Coding Solution

Stock Exchange Losses – solution CodinGame en C

Moyenrunning maximumsingle passarraysgreedyMis à jour le
Réponse courte

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

  1. 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.
  2. 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.
  3. 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.
  4. 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é

TempsO(n)
MémoireO(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

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.

Puzzles similaires

★ 5,0 · 16 avis · 928 utilisateurs Ajouter à Chrome