Kadaneovo maximální podpole

O(n)

Kadaneův algoritmus najde maximální součet libovolného souvislého podpole jedním lineárním průchodem. Udržuje běžící součet aktuálního okna; u každého prvku si položí jednoduchou otázku — táhne běžící součet pořád svou váhu? Pokud součet klesl na nulu nebo níž, předchozí část už může jen škodit, takže se zahodí a začne nové okno u aktuálního prvku. Jinak prvek okno prodlouží. Nejlepší kdy viděný běžící součet je odpověď. Je to učebnicový příklad dynamického programování destilovaného do dvou proměnných a pohání úlohy od oken zisku z akcií po analýzu obrazu a signálu. Zkus dopsat záporná čísla a uvidíš reset okna.

Pole
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Jdi zleva doprava a udržuj běžící součet aktuálního okna.
  2. Když běžící součet klesne na nulu či níž, zahoď ho a začni znovu u tohoto prvku.
  3. Jinak prvek přidej do okna.
  4. Sleduj nejlepší viděný běžící součet — ten úsek je maximální podpole (zvýrazněno).

Pseudokód

1kadane(a):                          # O(n)2  cur ← 0, best ← −∞3  for each x in a:4    if cur ≤ 0: cur ← x              # drop a spent prefix5    else: cur ← cur + x6    best ← max(best, cur)7  return best                        # max contiguous-subarray sum