Maximální podpole

Na vstupu je pole čísel, např. pole = [1, -2, 3, 4, -9, 6].

Úkol zní: najděte souvislé podpole tohoto pole s maximálním součtem prvků.

Napište funkci vraťMaxSoučetPodpole(pole), která tento součet vrátí.

Příklad:

          vraťMaxSoučetPodpole([-1, 2, 3, -9]) == 5 (součet zvýrazněných prvků)
vraťMaxSoučetPodpole([2, -1, 2, 3, -9]) == 6
vraťMaxSoučetPodpole([-1, 2, 3, -9, 11]) == 11
vraťMaxSoučetPodpole([-2, -1, 1, 2]) == 3
vraťMaxSoučetPodpole([100, -9, 2, -3, 5]) == 100
vraťMaxSoučetPodpole([1, 2, 3]) == 6 (vezmi vše)
        

Jsou-li všechny prvky záporné, znamená to, že nevezmeme žádný (podpole je prázdné), takže součet je nulový:

vraťMaxSoučetPodpole([-1, -2, -3]) = 0

Snažte se prosíme vymyslet rychlé řešení: O(n²) nebo dokonce O(n), jestliže to dokážete.

Otevřít pískoviště s testy.

Pomalé řešení

Můžeme spočítat všechny možné podsoučty.

Nejjednodušším způsobem je vzít každý prvek a počítat součty všech podpolí, která jím začínají.

Například pro [-1, 2, 3, -9, 11]:

          // Začínající -1:
-1
-1 + 2
-1 + 2 + 3
-1 + 2 + 3 + (-9)
-1 + 2 + 3 + (-9) + 11

// Začínající 2:
2
2 + 3
2 + 3 + (-9)
2 + 3 + (-9) + 11

// Začínající 3:
3
3 + (-9)
3 + (-9) + 11

// Začínající -9:
-9
-9 + 11

// Začínající 11:
11
        

Kód je ve skutečnosti vnořený cyklus: vnější cyklus prochází prvky pole, vnitřní počítá podsoučty počínaje aktuálním prvkem.

function vraťMaxSoučetPodpole(pole) {
  let maxSoučet = 0; // nevezmeme-li žádné prvky, vrátí se nula

  for (let i = 0; i < pole.length; i++) {
    let součetPevnýZačátek = 0;
    for (let j = i; j < pole.length; j++) {
      součetPevnýZačátek += pole[j];
      maxSoučet = Math.max(maxSoučet, součetPevnýZačátek);
    }
  }

  return maxSoučet;
}

alert( vraťMaxSoučetPodpole([-1, 2, 3, -9]) ); // 5
alert( vraťMaxSoučetPodpole([-1, 2, 3, -9, 11]) ); // 11
alert( vraťMaxSoučetPodpole([-2, -1, 1, 2]) ); // 3
alert( vraťMaxSoučetPodpole([1, 2, 3]) ); // 6
alert( vraťMaxSoučetPodpole([100, -9, 2, -3, 5]) ); // 100

Toto řešení má časovou složitost O(n²). Jinými slovy, když zvětšíme pole dvojnásobně, algoritmus bude pracovat čtyřikrát déle.

Pro velká pole (1000, 10000 nebo více prvků) mohou takové algoritmy vést k vážnému zpomalení.

Rychlé řešení

Budeme procházet prvky pole a pamatovat si aktuální částečný součet prvků v proměnné s. Bude-li s v některém bodě záporné, přiřadíme s=0. Odpovědí bude maximum všech takových s.

Pokud je popis příliš vágní, prosíme nahlédněte do kódu, je dosti krátký:

function vraťMaxSoučetPodpole(pole) {
  let maxSoučet = 0;
  let částečnýSoučet = 0;

  for (let prvek of pole) { // pro každý prvek pole
    částečnýSoučet += prvek; // přičteme jej do částečnýSoučet
    maxSoučet = Math.max(maxSoučet, částečnýSoučet); // zapamatujeme si maximum
    if (částečnýSoučet < 0) částečnýSoučet = 0; // je-li součet záporný, vynulujeme ho
  }

  return maxSoučet;
}

alert( vraťMaxSoučetPodpole([-1, 2, 3, -9]) ); // 5
alert( vraťMaxSoučetPodpole([-1, 2, 3, -9, 11]) ); // 11
alert( vraťMaxSoučetPodpole([-2, -1, 1, 2]) ); // 3
alert( vraťMaxSoučetPodpole([100, -9, 2, -3, 5]) ); // 100
alert( vraťMaxSoučetPodpole([1, 2, 3]) ); // 6
alert( vraťMaxSoučetPodpole([-1, -2, -3]) ); // 0

Tento algoritmus vyžaduje přesně 1 průchod polem, takže jeho časová složitost je O(n).

Podrobnější informace o algoritmu můžete najít zde: Maximum subarray problem (Problém maximálního podpole). Není-li vám stále jasné, proč to funguje, potom si prosíme projděte algoritmus na výše uvedených příkladech a podívejte se, jak funguje. Je to lepší než jakákoli slova.

Otevřít řešení s testy na pískovišti.