17. Nejkrásnější pobřeží

Vláda chudého ostrova v Karibiku nabízí zdarma pozemky na pobřeží pod podmínkou, že se o ně budeme starat. Udělali jsme si analýzu, které úseky jsou jak náročné na péči, a kolik by nám každý z nich mohl vynášet na turistickém ruchu. Chceme najít nejvýhodnější souvislý úsek pobřeží, který si pořídíme.

Vstupem programu je seznam čísel. Každé číslo udává odhadovaný měsíční příjem z určitého úseku pobřeží. Některá čísla můžou být záporná, pokud údržba převáží nad příjmem.

Výstupem programu je jedno číslo. Výstup udává největší měsíční příjem, jakého můžeme dosáhnout nákupem jednoho souvislého úseku pobřeží. Uvažujeme i úseky sahající přes okraj vstupního seznamu (pobřeží je spojené do kruhu) a úseky libovolné délky.