Zoptymalizuj algo do Oblicz podłańcuchów z maksimum - algorytm

Co będzie zoptymalizować / Smart algo, aby uzyskać maksymalną pod-sekwencję z następujących serii "n" liczb Przykład:

Input:             Index   0  1  2  3  4  5  6  7
Series -1  0  3 -2  5 -2  6  1

trials  :          start :4 end :7 total :10
start :6 end :7 total :7


Output (Max Total Sub-sequence):  start :2  ,end:7 , total:11

Odpowiedzi:

Możesz zaimplementować algorytm O (n) w łatwy sposób; Są dwa sposoby, o których mogę pomyśleć:

1) DP:

Niech dp [i] będzie długością maksymalnego podciągu kończącego się na elemencie i dp[0] = element[0]. I dla każdego i, dp[i] = max( dp[i - 1] + element[i], element[i] ). To dlatego, że masz dwie możliwości wyborudodanie bieżącego elementu do poprzedniego maksymalnego podciągu lub utworzenie nowego. Podejmij maksimum w stosunku do wszystkich, i to jest twoja odpowiedź. Możesz znaleźć początek i koniec, łatwo śledząc zmiany.

2) Prosty intuicyjny algorytm:

Przede wszystkim utwórz tablicę sum prefiksów, aby przedrostek [i] był sumą elementów 0...i. Teraz, jeśli masz podciąg od a do b, to jego suma jest oczywiście prefix[b] - prefix[a - 1] (a = 0 to specjalny przypadek, który można obsłużyćz łatwością ). Teraz załóżmy, że naprawiliśmy b, wtedy optymalny wybór powinien zminimalizować prefiks [a - 1]. Możemy więc powtórzyć cały proces, zachowując do tej pory minimalny przedrostek [j]. Odpowiedź jest po prostu maksymalna na wszystkich etapach, na każdym kroku: prefix[i] - prefix[j].

Oto pseudokod:

// Compute prefix sum array easily and trivially ( ask me if you want how )

int curMin = 0, answer = - INFINITY;

for i = 0 to n - 1

answer = max( answer, prefix[i] - curMin );

curMin = min( curMin, prefix[i] );

Istnieje algorytm liniowy. Zobacz na przykład to http://wordaligned.org/articles/the-maximum-subsequence-problem