cetate

Algoritmul, pas cu pas

Profitul unei submatrice e doar suma valorilor dintr-un dreptunghi. Dacă pregătim o sumă parțială 2D, putem afla profitul oricărui dreptunghi într-o singură scădere, instantaneu. Cu ea, cerința 1 devine banală: trecem prin toate pătratele $K \times K$ și ținem maximul.

Cerința 2 e provocarea reală — toate submatricele cu ambele laturi $\le K$. A le încerca pe toate ar fi $O(N^2 M^2)$, ordinul $10^{10}$ pentru $N = M = 400$: prea lent. Trucul e să nu privim o submatrice ca un dreptunghi liber în 2D, ci s-o „turtim" la o problemă pe un singur vector.