Spójny podciąg o maksymalnej sumie

Problem

Dostajesz ciąg n liczb całkowitych: a[1], a[2], a[3] … a[n], gdzie:
1 <= n <= 3*10^6
-10^9 <= t[i] <= 10^9
Musisz wypisać sumę ze spójnego podciągu o maksymalnej sumie.

Rozwiązanie

Czym jest spójny podciąg o maksymalnej sumie? Jest to taki fragment ciągu, którego suma jest największa. Jaki jest pierwszy rzucający się w oczy sposób na wyliczenie sumy ze spójnego podciągu o maksymalnej sumie? Rozważyć wszystkie możliwe podciągi i z każdego z nich policzyć sumę, a największą wziąć do wyniku. Jednak jest to rozwiązanie o złożoności O(n^2). Przy tak wysokim n-ie, czekalibyśmy bardzo długo na wykonanie programu. Musi więc istnieć jakieś inne rozwiązanie naszego problemu.

Algorytm będzie wyglądać następująco:

 

Jak działa ten algorytm? Będziemy szukać podciągu o maksymalnej sumie. Na początku nie dysponujemy takim (tzn. dysponujemy jedynie podciągiem o liczbie elementów 0, stąd początkowa suma też wynosi 0). Jeżeli będzie się nam opłacać przyłączyć nowy element do podciągu, tzn. po przyłączeniu rozważanego elementu do podciągu jego suma nie spadnie poniżej 0, to przyłączamy go, w przeciwnym wypadku usuwamy z podciągu wszystkie elementy, otrzymując pusty podciąg. Można pomyśleć: „ale po co przyłączać element, który zmniejszy sumę podciągu”? Sens takiego działania zostanie pokazany przez następujący przykład:

6  -1  3 // dotychczasowy podciąg; suma: 8
-3  8 // kolejne elementy

Jeżeli do dotychczasowego podciągu przyłączymy liczbę -3, to nie ma znaczenia, że suma się zmniejszyła, dlatego że być może później napotkamy na liczbę dodatnią, która w ostatecznym rozrachunku zwiększy sumę podciągu, w tym przypadku jest to liczba 8. Po każdym takim działaniu wyczyszczenia podciągu lub przyłączenia nowego podciągu, aktualizujemy nasz wynik.. Zauważ, że nie musimy tego podciągu  fizycznie przechowywać. Wystarczy, że będziemy mieć jedynie sumę jego elementów.

Przykład

10
-3 4 -1 2 -7 2 -1 5 -2 1

Wynik powinien wyjść 6. Jest to suma z następującego podciągu: 2 -1 5.

 

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

*