maksimumsummad

Maksimumsummad on mõiste matemaatikas ja arvutiteaduses, mis viitab suurimale võimalikule summeeritud väärtusele antud tingimustel. Kõige levinum tähendus on maksimaalse alamsumma probleem: antakse järjestatud arvude jada ning tuleb leida suurim summa, mis koosneb järjestikustest elementidest.

Kui numbreid võib olla nii positiivseid kui negatiivseid, võib maksimaalne summa olla negatiivne, kui kõik arvud on negatiivsed. Mõnede lahenduste puhul lubatakse tühi alamjadasumma, mille väärtus on 0; teistes definitsioonides peab alamjadasumma olema mitte-tühi.

Lahendused ja algoritmid: Kadane'i algoritm on kõige tuntum meetod maksimaalse alamsumma leidmiseks. See töötab lineaarajas ja põhineb dünaamilisel programmeerimisel: jälgitakse jooksvat summat ja sellest tulenevalt parimat leitud väärtust ning iga sammu korrigeeritakse vastavalt. Üldiselt on ajakompleksus O(n) ning mäluvajadus minimaalne.

Variaadid ja laiendused hõlmavad näiteks: tsüklilist (ringilist) järjestust, kus maksimaalne alamsumma tuleb leida nii, et subarray võib kattuda ümber ülemise piiriga; selliste lahenduste jaoks kasutatakse sageli Kadane'i metoodika juhtpaneeli ning lisalugusid kogu summa ja minimaalne alamsumma abil; samuti on olemas variandid, kus leitakse maksimaalne summa kahe mitteülekatuva alamsumma vahel või piirangutega alaosade haldamine.

Rakendused ulatuvad finantsanalüüsist signaalitöötluseni ning need tööriistad aitavad hinnata ajaperioodide või tegurite maksimaalset kogusummat. Seisuga seosed hõlmavad alamsumma, prefiks-summad ja erinevaid optimeerimisprobleeme.