- Meilleur moment pour acheter et vendre des actions II
La stratégie consiste à cumuler tous les gains quotidiens positifs. Pour chaque jour, on calcule la différence avec le jour précédent. Si cette différence est positive, on l'ajoute au profit total. Cette décision locale optimale garantit un profit global maximal dans ce problème.
class Solution {
public:
int maxProfit(vector<int>& prix) {
int gain = 0;
int n = prix.size();
for (int j = 1; j < n; ++j) {
int diff = prix[j] - prix[j - 1];
if (diff > 0) gain += diff;
}
return gain;
}
};
</int>
- Jeu de sauts
Plutôt que de simuler chaque saut, on maintient la portée maximale atteignable depuis le début du parcours. En itérant sur les indices, on vérifie que l'index courant reste dans cette portée et on l'étend si possible. Si la portée couvre le dernier index, le parcours est réalisable.
class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size();
if (n <= 1) return true;
int limite = 0;
for (int i = 0; i <= limite; ++i) {
limite = max(limite, i + nums[i]);
if (limite >= n - 1) return true;
}
return false;
}
};
- Jeu de sauts II
L'objectif est de déterminer le nombre minimal de sauts pour atteindre la fin du tableau. On utilise deux indicateurs : la limite de l'étape en cours et la limite la plus lointaine atteignable. Lorsqu'on atteint la limite courante, on effectue un saut et on met à jour cette limite avec la portée lointaine, ce qui minimise le nombre total de sauts.
class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size();
if (n == 1) return 0;
int etendueActuelle = 0, etendueSuivante = 0, sauts = 0;
for (int i = 0; i < n; ++i) {
etendueSuivante = max(etendueSuivante, i + nums[i]);
if (i == etendueActuelle) {
if (etendueActuelle != n - 1) {
sauts++;
etendueActuelle = etendueSuivante;
} else {
break;
}
}
}
return sauts;
}
};
- Maximiser la somme après K inversions
Deux choix gloutons s'appliquent ici. On trie d'abord les nombres par valeur absolue décroissante, puis on inverse les nombres négatifs pour transformer les plus grandes valeurs absolues en positives. Si des opérations restent après avoir traité tous les négatifs, l'ordre par valeur absolue garantit que l'inversion finale touche le plus petit élément. Un nombre impair d'opérations restantes nécessite une seule inversion supplémentaire.
class Solution {
private:
static bool comparer(int a, int b) {
return abs(a) > abs(b);
}
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(), nums.end(), comparer);
for (size_t i = 0; i < nums.size(); ++i) {
if (nums[i] < 0 && k > 0) {
nums[i] = -nums[i];
k--;
}
}
if (k % 2 == 1) {
nums.back() = -nums.back();
}
int total = 0;
for (int v : nums) total += v;
return total;
}
};