De ce contează?
Ai o hartă dreptunghiulară cu valoarea fiecărei zone: unele celule aduc câștig (verde), altele pierdere (roșu). Vrei să decupezi cel mai „bogat” dreptunghi de pe hartă — regiunea continuă a cărei sumă de valori e maximă. Submatricele posibile sunt mult prea multe ca să le verifici una câte una. Trucul: nu cauți direct dreptunghiul, ci reduci harta 2D la o problemă 1D pe care o știi deja.
Intuiția
Ideea-cheie este să transformi o problemă 2D pe care n-o știi într-una 1D pe care o știi deja. Fixezi o pereche de linii — o linie de sus și una de jos. Atunci orice submatrice cuprinsă între ele e descrisă complet de intervalul de coloane ales. Dacă comprimi fiecare coloană într-un singur număr (suma celulelor ei dintre cele două linii), problema devine: ce interval continuu din acest șir de sume are suma cea mai mare? Asta e exact Kadane 1D, pe care îl ai din lecția despre secvența de sumă maximă.
Mecanismul în trei mișcări: (1) fixezi perechea de linii (sus, jos);
(2) comprimi fiecare coloană într-o singură sumă — celulele ei dintre cele
două linii; (3) rulezi Kadane 1D pe șirul de sume pe coloane. Repeți pentru
toate perechile de linii și reții maximul global. Tot misterul 2D dispare:
alegerea coloanelor de start și de stop e o secvență de sumă maximă obișnuită.