Zadanie

Rok 2018 (rekonštruované podľa dobových záznamov):

“Tak, vítam Vás všetkých na Rade Trojstenu. Máme dnes celkom veľa vecí na práci. Takmer polovica pozícií v Trojstene je neobsadených… Hľadáme napríklad hlavného vedúceho KMS, vedúcich FKS, dievčatá do KSP,…”

“Muhahahahaa” pomyslel si Krtko. “Konečne sa zmocním všetkých pozícií v Trojstene. Teda, nie všetkých, ale len tých cool. Napríklad hlavný vedúci KMS naozaj nie je cool pozícia…”

“Takže, chce si niekto zobrať pozíciu dievčaťa v KSP?”

“Ja by som si to zobral”, ozval sa Krtko.

“Hlavného vedúceho KMS?”

“Nie, toto nechcem…”, povedal Krtko.

“Ale takto to nefunguje, Krtko… Ak si zoberieš nejakú pozíciu, tak si musíš zobrať všetky pozície od nej, až po poslednú.”

“No dobre, ako myslíte…”

…

Už dlhé roky sa v Trojstene traduje táto legenda, ale nikto doteraz nevie ako veľmi cool boli pozície, ktoré si Krtko zobral. Z dobových záznamov sa zachoval len počet pozícií, ktoré boli v ponuke, a cool-ovosť týchto pozícií. Vedeli by ste z týchto údajov vypočítať najväčšiu možnú coolovosť pozícií, ktoré si mohol Krtko zobrať?

Úloha:

Pre zadané coolovosti pozícií na vstupe, vypíšte maximálnu možnú coolovosť, ktoré je rovná súčtu coolovosti pozícií na neprázdnom intervale, ktorý končí na poslednom prvku poľa.

Formát vstupu

Na prvom riadku vstupu sa nachádza číslo \(n \leq 100000\) - počet pozícií, ktoré boli ponúknuté Krtkovi. Na druhom riadku sa nachádza \(n\) medzerou oddelených čísel, \(c_i\): \(-100000 \leq c_i \leq 100000\).

Formát výstupu

Vypíšte jedno číslo, maximálnu možnú coolovosť pozícií, ktore mohol Krtko získať.

Príklad

Input:

5
1 2 -5 10 2

Output:

12

Input:

3
10 -8 10

Output:

12

Je niekoľko spôsobov, ako sa na túto úlohu pozerať. Líšia sa časovou a pamäťovou zložitosťou.

Priamočiare riešenie

Pre každý možný začiatok intervalu potrebujeme zistiť, aký je súčet prvkov po posledný a následne z nich vybrať maximálny. Toto riešenie zaberie \(O(n)\) pamäte, lebo si pamätáme celé pole, a \(O(n^2)\) času, lebo pre každý prvok musíme sčítať všetky ďalšie. Dokopy, za celý beh programu počet prvkov, ktoré potrebujeme sčítať vieme vyjadriť ako \(\frac{n \cdot \left(n-1\right)}{2}\), čo je asymptoticky \(n^2\).

Ako zlepšiť časovou zložitosť

To, na čom náš kód trávi priveľa času, je to, že každý interval počíta odznovu. Na to, aby sme nemuseli vždy počítať súčet celého nového intervalu, si stačí uvedomiť, že ako prechádzame intervaly od najdlhšieho, tak nový interval je vždy len o jeden prvok kratší ako ten starý, resp., ten starý je o jeden prvok dlhší. To znamená, že ak sa budeme pozerať na intervaly od najkratšieho, (ako prvý sa pozrieme na ten, ktorý má len jeden prvok), tak súčty všetkých intervalov, ktoré končia na poslednom prvku poľa zistíme na \(n\) krokov, kde v každom kroku pripočítame k aktuálnemu súčtu ďalší prvok. Pamäťová zložitosť bude \(O(n)\), lebo stále si musíme pamätať celé pole, ale časová zložitosť bude už iba \(O(n)\).

Ako to robiť bez nutnosti pamätania všetkých súčtov

Toto riešenie samozrejme môže mať veľa variácií, napríklad namiesto hľadania intervalu s čo najväčším súčtom, ktorý končí na poslednom prvku poľa, môžeme hľadať interval od začiatku, ktorého suma je čo najmenšia. V takomto prípade je výsledok súčet celého poľa mínus súčet intervalu s najmenším súčtom.

Toto dokonca dokážeme urobiť v pamäti \(O(1)\), a čase \(O(n)\), ak načítavame prvky postupne, po jednom.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.