L'algorithme de sous-séquence contiguë de valeur maximale

Question

L'entrée de ce problème est un tableau A[1...n] de nombres réels. Votre besoin de trouver quelle est la valeur la plus élevée peut être obtenu en additionnant tous les nombres d'une sous-séquence contiguë A[i],A[i+1],...A[j] de A. Si A ne contient pas de nombres négatifs, le problème est trivial et peut être résolu en additionnant tous les éléments de A. Il devient plus difficile quand A contient un mélange de nombres positifs et négatifs bien. Par exemple, pour A = [-2,11,-4,13,-5,-3], la solution est 20(11-4 + 13 = 20). Pour A = [-2,1,-3,4,-1,2,1,-5,4], la solution est 6(4-1 + 2 + 1 = 6). La somme des nombres d'une sous-séquence vide est 0.

Il existe une solution de force brute qui permet de résoudre ce problème dans O (n^3), mais il est également possible de résoudre le problème dans le temps linéaire.

1. Concevoir un algorithme qui résout le problème décrit ci-dessus en temps linéaire. Présentez votre algorithme en pseudo-code.
2. Expliquez brièvement comment et pourquoi votre algorithme fonctionne.
3. Donnez une brève explication de la raison pour laquelle votre algorithme s'exécute en temps linéaire.

Answer 1

Si nous ne prenons pas de point (de sorte que la solution est un vide sous-tableau), nous avons 0 comme une solution. C'est pourquoi la règle est la suivante:

When running `sum` drops to `0` or below, restart summing. 

Un peu moment délicat est en somme que nous courons dans un nombre négatif:

3, 4, 5, -1 ... 

nous pouvons soit laisser (et ont 3 + 4 + 5 == 12) ou prendre en espérant que les nombres positifs apparaîtront bientôt:

3, 4, 5, -1, 100, 200, 300 

pour résoudre cette ambiguïté, nous pouvons simplement mémoriser le meilleur sum jusqu'à un result et continuer à sommer. C mise en œuvre de #:

private static double Solution(IEnumerable<double> source) { 
    // We can guarantee 0 (for empty subarray) 
    double result = 0; 
    double sum = 0; 

    // Linear: all we have to do is to scan the collection 
    foreach (var item in source) 
    if (sum + item <= 0) // when sum drops to zero 
     sum = 0;   // ... restart summing 
    else { 
     sum += item; 

     if (sum > result) // update the best sum so far on each decision 
     result = sum; 
    } 

    return result; 
} 

Tests:

// 6 
Console.WriteLine(Solution(new double[] { -2, 1, -3, 4, -1, 2, 1, -5, 4 })); 
// 20 
Console.WriteLine(Solution(new double[] { -2, 11, -4, 13, -5, -3 }));