Maximális résztömbök

Talán hallottál már a „maximális összegű résztömb problémájáról”, például az egyetemi alapképzés Algoritmusok kurzusán. A feladat a következő: egy n egészet tartalmazó A tömb esetén meg kell találni A-nak egy olyan összefüggő résztömbjét, amelyben az elemek összege maximális. Ha például adott az alábbi tömb:

A := [-2, 3, 5, -7, 8, 13, -20, 14, 1],

a megoldás a második indexű elemtől (3) a hatodik indexű elemig (13) tartó résztömb, amelyben az elemek összege 22. A feladat megoldható „oszd meg és uralkodj” módszerrel O(n log n) időben, vagy dinamikus programozással O(n) időben.

Mivel te erős vagy az algoritmusokban, nyilván mindkét megközelítést jól ismered, ezért itt most nem magyarázzuk el őket. A csoporttársad, Steve, aki nem olyan erős az algoritmusokban, neked henceg a maximális résztömb problémáról. Azt állítja, hogy nemcsak a maximális résztömb problémát tudja megoldani lineáris időben, hanem az általa „k-maximális résztömb problémának” nevezett feladatot is, SZINTÉN lineáris időben! Mi az a „k-maximális résztömb probléma”? — kérded. Steve leereszkedő hangnemben magyarázza: Ez a maximális résztömb probléma természetes általánosítása. Egy n egészet tartalmazó A tömb esetén meg kell találni A-nak k darab diszjunkt, összefüggő résztömbjét úgy, hogy ezek elemeinek összege maximális legyen.

Egyáltalán nem vagy meggyőződve arról, hogy Steve tudja, hogyan kellene megoldani a „k-maximális résztömb problémát” lineáris időben, ha létezik egyáltalán lineáris idejű megoldás. Te azonban minden Algoritmusok előadáson ott voltál, ami közel végtelenszer több Steve jelenléteinek számánál, ezért úgy gondolod, hogy ha valaki kompetens a témában, az valószínűleg te vagy.

Úgy döntesz, hogy írsz egy programot a „k-maximális résztömb probléma” megoldására. Ezt a programot használhatod Steve vélhetően hibás algoritmusának ellenőrzésére. Az egyszerűség kedvéért úgy írod meg a programot, hogy csak az optimális megoldáshoz tartozó összeget írja ki. Később átírhatod, ha magára a megoldásra lenne szükség. Úgy határozol továbbá, hogy az algoritmusodat akkor tekinted elegendően hatékonynak, ha a futási ideje korlátozható egy n-ben és k-ban kicsi polinommal. Úgy gondolod, hogy egy ténylegesen helyes lineáris idejű megoldással előállni vélhetően sokáig tartana számodra, te viszont csak legfeljebb úgy öt órát szeretnél a kódolással tölteni.

A bemenet specifikációja

A bemenet két sorból áll. Az első sor az n és k egész számokat tartalmazza (1 ≤ k ≤ n ≤ 5 000). A második sorban n egész szám áll, amelyek az A tömböt reprezentálják. Az A tömbben szereplő egész számok –10⁹ és 10⁹ közé esnek.

A kimenet specifikációja

A kimenetre az A tömb k darab diszjunkt, összefüggő résztömbjében található elemek lehetséges maximumát kell kiírni. Bár a résztömböknek diszjunktaknak kell lenniük, egy résztömb zárulhat az i indexű elemnél, egy másik résztömb pedig kezdődhet az i + 1 indexű elemnél. A résztömbök nem lehetnek üresek.