Stock Exchange Losses – solution CodinGame en C
On parcourt les valeurs une seule fois en gardant le plus haut vu jusque-là. Pour chaque nouvelle valeur, la pire perte qui s'y termine vaut value - highestSoFar ; on conserve le minimum de ces différences en partant de 0, et on l'affiche, ce qui donne un nombre négatif ou 0 quand le cours ne baisse jamais. La solution est en O(n) en temps et O(1) en mémoire.
L'énoncé
On reçoit la liste chronologique de n cours boursiers (n jusqu'à 100 000, chaque valeur étant un entier positif inférieur à 2^31). Il faut trouver la plus grande perte qu'un investisseur pourrait subir en achetant à un moment et en revendant plus tard.
La réponse est la différence v[j] - v[i] la plus négative avec i < j, affichée comme un entier négatif. Si les valeurs ne baissent jamais, il n'y a pas de perte et il faut afficher 0.
La démarche, étape par étape
- Reformuler le problèmeOn cherche le minimum de v[j] - v[i] pour i < j. Pour un jour de vente j fixé, le pire jour d'achat est la plus haute valeur qui le précède : il suffit donc du maximum courant.
- Un seul passageOn parcourt les valeurs, on met à jour maxSoFar = max(maxSoFar, v) et on calcule v - maxSoFar. On garde la plus petite différence rencontrée, initialisée à 0.
- Afficher le résultat tel quelLa meilleure différence est déjà négative (ou nulle), donc on l'affiche directement. Partir de 0 gère le cas « aucune perte » sans branche spéciale.
- Lire les valeurs efficacementToutes les valeurs sont sur une ligne. Découper la ligne (ou boucler avec scanf en C) suffit ; il n'est jamais nécessaire de stocker le tableau.
Complexité
O(n)O(1)Chaque valeur est lue et comparée une fois et seuls deux nombres sont conservés. La vérification brute de toutes les paires est en O(n^2), soit environ 5 * 10^9 comparaisons pour n = 100 000, ce qui dépasse le temps.
Code de la solution
Stock Exchange Losses – C
La version C lit toute la ligne et la découpe avec strtok et atoi. Au lieu d'un maximum courant, elle suit un couple « sommet courant et plus basse valeur depuis ce sommet » et clôt le segment dès qu'un nouveau sommet apparaît, ce qui est équivalent et correct.
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>
int main(int argc, char **argv)
{
// number of stock values
int N;
scanf("%d\n", &N);
/* as each stock value is under 2^31 which is roughly 4*10^9,
15 chars per value is largely enough*/
char line[15*N];
fgets(line,15*N,stdin);
/* currentMax and currentMin will store the local minimum and maximum
stock values, maxLoss will store the maximum loss found yet */
int stockValue, maxLoss, currentMax, currentMin;
maxLoss = currentMax = 0;
currentMin = INT_MAX;
// Uses strtok to read all the stock values
char *tok;
tok = strtok(line," ");
for (int i = 0 ; i < N ; i++) {
stockValue = atoi(tok);
/* a new peak: the drop measured from the old peak is final, store it and restart from here */
if (stockValue > currentMax) {
if (currentMax-currentMin > maxLoss)
maxLoss = currentMax-currentMin;
currentMax = currentMin = stockValue;
}
/* still below the current peak: remember the lowest point since that peak */
else if (stockValue < currentMin)
currentMin = stockValue;
tok = strtok(NULL," ");
}
/* the last segment never closed inside the loop, so check it once more */
if (currentMax-currentMin > maxLoss)
maxLoss = currentMax-currentMin;
/* maxLoss is a positive drop (0 if none); the expected output is negative */
printf("%d\n",-maxLoss);
return EXIT_SUCCESS;
}
Erreurs fréquentes
- Maximum global moins minimum globalAvec les valeurs 1 2 4 4 5, le minimum global précède le maximum, donc max - min n'est pas une perte du tout. Le point bas doit venir après le point haut, d'où le maximum courant.
- Mal réinitialiser le minimumUne approche « sommet et creux » doit clore la chute courante avant de passer à un nouveau sommet ; oublier la vérification finale après la boucle rate une perte en toute fin de série, comme 3 2 4 2 1 0.
- Afficher un nombre positif ou -0La sortie attendue est la perte sous forme négative, et 0 s'il n'y en a pas. Afficher la valeur absolue, ou un -0 flottant, échoue aux tests.
- Force brute quadratiqueComparer toutes les paires passe les petits tests mais pas celui à 100 000 valeurs. Un seul passage avec un maximum courant est à la fois plus simple et rapide.
Pour aller plus loin
Ce puzzle est le miroir de la question d'entretien classique « best time to buy and sell a stock » : là, on cherche max(v[j] - v[i]) avec un minimum courant, ici min(v[j] - v[i]) avec un maximum courant. Y voir un extremum glissant plutôt qu'une recherche sur des paires est toute l'astuce, et elle se généralise : le même schéma donne le drawdown maximal d'une courbe de portefeuille, et avec des sommes préfixes il donne la somme maximale de sous-tableau (algorithme de Kadane). Le débordement n'est pas un souci ici même en int 32 bits, car les deux valeurs sont positives et inférieures à 2^31, donc leur différence reste dans la plage du int ; il le devient si l'on adapte le code à des valeurs pouvant être négatives.
Questions fréquentes
Que faut-il afficher si le cours ne fait que monter ?
Il faut afficher 0. Initialiser la meilleure différence à 0 donne ce résultat automatiquement.
Pourquoi la réponse n'est-elle pas simplement le maximum moins le minimum ?
Parce que la vente doit avoir lieu après l'achat. Le minimum peut précéder le maximum, et dans ce cas la paire est un gain, pas une perte.
Faut-il des entiers 64 bits ?
Non. Toutes les valeurs sont positives et inférieures à 2^31, donc toute différence tient dans un int signé 32 bits.