Wskazówka do zadania

Question

Mam zadanie ktore polega na tym że mam tablice n elemntowa i mam podac jaka najwieksza wartosc mozna uzyskac sumujac dowolna liczbe sąsiednich liczb np

n=7

4 1 2 -3 5 7 -20

wynik =16 bo 4+1+2-3+5+7=16

Nie chce programu prosze tlyko o jakas wsakzowke gdzie szukac? (jestem poczatkujacym) czy to cos z programowania dynamicznego?

Zadanie chce rozwiazac dla n<=10000000  wiec potrzebna mi jakas metoda.

Gdzie szukac informacji - co googleować?

Answer 1

Wskazówka: skoro należy uzyskać jak największą sumę, niezależnie od ilości liczb którą będziemy sumować, to im więcej liczb nieujemnych weźmiemy, tym większy wynik dostaniemy. Tak więc każda konsekutywna liczba naturalna będzie pożądana. Problem pojawia się wtedy, gdy natkniemy się na liczbę ujemną. Zadanie można by więc uprościć z:

4 1 2 -3 5 7 -20

do:

7 -3 12 -20

I trzeba by dalej coś pokombinować, przy czym sumowanie sąsiednich liczb ujemnych już wcale tak oczywiste nie jest.

Answer 2

To jeden z podstawowych i całkiem fajnych problemów algorytmicznych. Charakteryzuje się tym, że istnieje na niego masa różnych rozwiązań. Od najgorszych o złożoności O(n^3) gdzie przechodzisz całą tablicę sprawdzając każdą możliwą sumę na przedziale. Przez trochę szalone rozwiązania rekurencyjne o złożoności O(n log n) - (tu algorytm jest trochę dziwny i jest można powiedzieć trochę sztuką dla sztuki, więc nie będę się rozwodzić, jeśli byś jednak bardzo chciał to daj znać w komentarzu)... aż wreszcie najbardziej efektywny algorytm (i o dziwo koncepcyjnie na prawdę baaaarrrdzooo prosty) o złożoności liniowej: O(n).

W ostatnim z powyższych wystarczy zastosować coś takiego: idę sobie po tablicy od lewej do prawej zliczając sumę liczb, które napotkałem. Jednocześnie mam zmienną, w której pamiętam największą do tej pory napotkaną sumę liczb. Przy każdym kroku, jeśli suma się powiększyła aktualizuje tego mojego maxa. Nie ma co się przejmować ujemnymi liczbami, bo liczby dodatnie następujące po nich (tak jak i w Twoim przykładzie) mogą, że tak powiem "zadość uczynić" za te ujemne. Ale uwaga! Jeśli w pewnym momencie suma stanie się ujemna to w aktualnej sumie zapominamy o wszystkich liczbach do tej pory, bo wiadomo, że nie opłaca nam się ich brać, bo tylko obniżają potencjalną sumę.

Pozdrawiam,