De ce contează?
Conduci pe o autostradă lungă și la fiecare kilometru ai fie un câștig (o benzinărie ieftină), fie o pierdere (un drum cu taxă). Vrei să găsești tronsonul continuu de drum pe care câștigul tău net e cel mai mare. Dacă mergi pe o porțiune și ajungi „în minus” față de unde ai pornit, nu are rost să tragi acea pierdere mai departe: e mai bine să consideri că un tronson nou începe chiar de aici.
Intuiția
Ai un vector cu numere pozitive și negative și cauți secvența continuă (un interval de poziții vecine) cu suma cea mai mare. Imaginea cheie: parcurgi vectorul o singură dată ținând o „sumă curentă”. Atâta timp cât suma curentă te ajută, o duci mai departe. În clipa în care ea devine negativă, te trage în jos — așa că o arunci și pornești o secvență nouă din elementul curent.
La fiecare poziție ai exact o decizie: extinzi secvența curentă adăugând v[i],
sau iei de la capăt cu v[i] singur. Cheia: dacă suma curentă a ajuns negativă,
nu mai poate ajuta nicio secvență viitoare — o duci cu tine doar ca să scazi. Atunci
o arunci și pornești curat din v[i].