Programátorské strategie

Úloha Maximalizujte svůj zisk

Příběh:

Se soutěžemi se v televizi roztrhl pytel. Je na čase, abyste si vydělali také vy. Otázky jsou pro vás naprosto triviální a přichází čas vybrat si odměnu. Přivedou před vás n asistentek. Asistentky se drží za ruce a každá má na krku pověšenou ceduli s celočíselnou sumou, kterou získáte (kladné číslo) nebo naopak ztratíte (záporné číslo), když si tuto asistentku vyberete. Můžete si vybrat jakýkoliv počet asistentek, ale jejich spojené ruce smíte přerušit max. na dvou místech, tedy posloupnost odměn, kterou si vyberete, musí být spojitá, ale může být libovolně dlouhá. Asistentky nezískáváte, pouze sumy výher, takže jiná než finanční kritéria není třeba brát v úvahu.

Váš úkol založený na tomto příběhu je následující:

1. Vyřešte tuto úlohu jednoduchým, jasným a správným O(n²) algoritmem za 3 body.
2. Vyřešte tuto úlohu správným O(n log n) algoritmem na principu D&C za 6 bodů. (D&C se k tomuto problému moc nehodí a je těžké ho použít, tím zvědavější jsem na vaše případné řešení.
3. Pokud zdůvodníte, proč se D&C k úloze nehodí, dostanete 2 body (za podmínky, že to kromě psaní zdůvodnění budete řešit nějaký další bod této úlohy  ;-)
4. Vyřešte úlohu správným O(n) algoritmem na principu DP za 4 body.

Pro získání výše uvedených bodů stačí odevzdat algoritmus. Pokud úlohu dotáhnete až do implementace, získáte navíc 5 bodů. Pokud půjdete na úlohu 2 nebo 3, můžete si přovydělat prezentací na cvičení za 3 body, za vítězství v soutěži algoritmů podle počtu prezentovaných prací je možný další bodový zisk.