Suurin osasumma (Maximum Subarray) — interaktiivinen demo

Algoritmit: Kadane (O(n)) vs Bruteforce (O(n²))

Syötä kokonaislukutaulukko (pilkuilla erotettu). Esim. 31,-41,59,26,-53,58,97,-93,-23,84 Koko:

Tulos

Syöte

Suurin osasumma (Kadane)

—

Osavektorin indeksit

—

Suoritusten määrä (Kadane — askelmäärä)

—

Suurin osasumma (Bruteforce)

—

Suoritusten määrä (Brute force)

—

Algoritmien tehokkuus:

Kadane: O(n) — yhdellä läpikäynnillä, muistivaatimus O(1).
Brute force: O(n²) — kaikkien alitaulukoiden tarkastus.

Tässä sovelluksessa suoritusten määrät on laskettu yksinkertaisella "askel"-mallilla:
- lasketaan peritaktisesti silmukan iteraatiot, vertailut ja summaukset.

Selitys ja metrikkat

Kadane-algoritmi käy taulukon läpi kerran, pitää juoksevaa summaa ja nollaa sen, jos se laskee alle 0. Bruteforce laskee kaikkien mahdollisten osataulukkojen summat.

Mitä lasken "suorituksina"

- Iteraatio: silmukan läpikäynti
- Vertailu: if-ehto
- Lisäys: summa + arvo
- Tallennus: muuttujan päivitys

Nämä on summattu yhteen yksinkertaiseksi "op-count" -luvuksi, joka antaa karkean vertailevan käsityksen.

Tulosteen visualisointi

Visualisointi korostaa löydetyn maksimialijonon taulukossa.