Eng katta qism-matritsa

$N \times M$ o'lchamli butun sonli matritsa berilgan. Elementlari yig'indisi eng katta bo'lgan to'g'ri to'rtburchakli qism-matritsani toping (kamida bitta element). Shu yig'indini chiqaring.

Birinchi qatorda $N$ va $M$ ($1 \le N, M \le 100$). Keyingi $N$ ta qatorning har birida $M$ ta butun son ($|a_{i,j}| \le 10^4$).

Bitta son — eng katta yig'indi.

Barcha to'rtburchaklarni 2D prefiks bilan ko'rib chiqish $O(N^2 M^2) = 10^8$. Tezroq: yuqori $r_1$ va pastki qatorlarni tanlang; har bir ustunning qismidagi yig'indisi (ustun bo'yicha prefiks bilan ) bir o'lchamli massiv hosil qiladi. Unda eng katta qism-massivni Kadane bilan da toping. Jami .