Énoncé du problème

Vous disposez d'un tableau d'entiers cardPoints représentant les points de chaque carte disposées en ligne. À chaque étape, vous pouvez prendre une carte soit au début, soit à la fin de la ligne. Vous devez prendre exactement k cartes au total.

Votre score final correspond à la somme des points de toutes les cartes que vous avez récupérées. L'objectif est de déterminer le score maximal que vous pouvez obtenir.

Exemples d'entrée et de sortie

Exemple 1 :

Entrée : cardPoints = [1,2,3,4,5,6,1], k = 3
Sortie : 12
Explication : La stratégie optimale consiste à prendre les trois cartes les plus à droite, ce qui donne 1 + 6 + 5 = 12.

Exemple 2 :

Entrée : cardPoints = [2,2,2], k = 2
Sortie : 4
Explication : Peu importe les deux cartes choisies, la somme sera toujours de 4.

Exemple 3 :

Entrée : cardPoints = [9,7,7,9,7,7,9], k = 7
Sortie : 55
Explication : Puisque k est égal à la longueur du tableau, vous devez prendre toutes les cartes. Le score est la somme totale.

Contraintes :

• 1 <= cardPoints.length <= 10^5
• 1 <= cardPoints[i] <= 10^4
• 1 <= k <= cardPoints.length

Analyse et Approche Algorithmique

Choisir k éléments aux extrémités du tableau pour maximsier leur somme équivaut à choisir un sous-tableau continu de longueur n - k (où n est la taille totale du tableau) pour minimiser sa somme. La somme maximale recherchée est alors simplement la somme totale du tableau moins cete somme minimale.

L'algorithme de la fenêtre glissante (sliding window) est la méthode la plus efficace pour résoudre ce problème. Voici la démarche :

1. Calculer la somme des n - k premiers éléments pour initialiser la fenêtre.
2. Faire glisser cette fenêtre d'un élément vers la droite jusqu'à atteindre la fin du tableau. À chaque déplacement, on ajoute le nouvel élément entrant et on soustrait l'élément sortant.
3. Conserver la trace de la somme minimale rencontrée pendant ce glissement.
4. Le résultat final est la somme totale du tableau moins cette somme minimale.

Implémentations

C++

#include <vector>
#include <algorithm>

class CardGameSolver {
public:
    int calculateMaxPoints(const std::vector<int>& pointsArray, int cardsToPick) {
        int totalCards = pointsArray.size();
        int windowSize = totalCards - cardsToPick;
        
        if (windowSize == 0) {
            int total = 0;
            for (int val : pointsArray) total += val;
            return total;
        }

        int currentWindowSum = 0;
        int totalSum = 0;
        
        for (int i = 0; i < totalCards; ++i) {
            totalSum += pointsArray[i];
            if (i < windowSize) {
                currentWindowSum += pointsArray[i];
            }
        }
        
        int minWindowSum = currentWindowSum;
        
        for (int i = windowSize; i < totalCards; ++i) {
            currentWindowSum += pointsArray[i] - pointsArray[i - windowSize];
            minWindowSum = std::min(minWindowSum, currentWindowSum);
        }
        
        return totalSum - minWindowSum;
    }
};

Python

from typing import List

class CardGameSolver:
    def calculateMaxPoints(self, pointsArray: List[int], cardsToPick: int) -> int:
        totalCards = len(pointsArray)
        windowSize = totalCards - cardsToPick
        
        if windowSize == 0:
            return sum(pointsArray)
        
        currentWindowSum = 0
        totalSum = 0
        
        for i in range(totalCards):
            totalSum += pointsArray[i]
            if i < windowSize:
                currentWindowSum += pointsArray[i]
                
        minWindowSum = currentWindowSum
        
        for i in range(windowSize, totalCards):
            currentWindowSum += pointsArray[i] - pointsArray[i - windowSize]
            if currentWindowSum < minWindowSum:
                minWindowSum = currentWindowSum
                
        return totalSum - minWindowSum

Analyse de la Complexité

• Complexité temporelle : O(N), où N est la longueur du tableau cardPoints. Le tableau est parcouru un nombre constant de fois.
• Complexité spatiale : O(1). Seules quelques variables scalaires sont utilisées pour maintenir les sommes et les indices, sans nécessiter de structure de données supplémentaire proportionnelle à la taille de l'antrée.