Энг катта қисм-матрица

$N \times M$ ўлчамли бутун сонли матрица берилган. Элементлари йиғиндиси энг катта бўлган тўғри тўртбурчакли қисм-матрицани топинг (камида битта элемент). Шу йиғиндини чиқаринг.

Биринчи қаторда $N$ ва $M$ ($1 \le N, M \le 100$). Кейинги $N$ та қаторнинг ҳар бирида $M$ та бутун сон ($|a_{i,j}| \le 10^4$).

Битта сон — энг катта йиғинди.

Барча тўртбурчакларни 2D префикс билан кўриб чиқиш $O(N^2 M^2) = 10^8$. Тезроқ: юқори $r_1$ ва пастки $r_2$ қаторларни танланг; ҳар бир устуннинг $r_1 \ldots r_2$ қисмидаги йиғиндиси (устун бўйича префикс билан $O(1)$) бир ўлчамли массив ҳосил қилади. Унда энг катта қисм-массивни Kadane билан $O(M)$ да топинг. Жами $O(N^2 M)$.

Ҳамма элемент манфий бўлса, жавоб — энг катта элемент. Биринчи мисолда жавоб $15$: $(2, 1)$ дан $(4, 2)$ гача.

Манба: acmp.ru, 115-масала, UVa 108.