Maximum Submatrix Sum

Interview

Time limit0.2sMemory limit1024 MB

Summary

Given an N by M integer matrix, find the maximum sum of any contiguous rectangular submatrix, where the empty submatrix counts as 0.

Level: Medium5 of 10
Topics: Dynamic programming, Prefix sum, Matrix
Solved: No attempts yet

Problem

You are given an $N \times M$ matrix $A$ . Find the maximum sum of any subrectangular submatrix of this matrix.

Here, a subrectangular submatrix is a contiguous submatrix formed by selecting a rectangular section of the given matrix $A$ . It includes all rows and columns between two specified pairs of indices $(r_1, c_1)$ and $(r_2, c_2)$ , where $1 \le r_1 \le r_2 \le N$ and $1 \le c_1 \le c_2 \le M$ . The empty submatrix is also allowed.

Input

The first line of input contains two space-separated integers: $N$ and $M$ , the size of the matrix. ( $1 \le N \le M \le 100\,000;$ $1 \le NM \le 100\,000$ )

The next $N$ lines of input contain $NM$ integers, where each line has $M$ space-separated integers, denoting the values of the matrix. The $j$ -th integer of the $i$ -th line is $A_{ij}$ . ( $-10\,000 \le A_{ij} \le 10\,000$ )

Output

Output the maximum sum of any subrectangular submatrix on a single line.

Hint

(For Sogang students:) This problem is an adapted version that fits the format of a general programming contest. In the exam, the original scoring was:

Subtask 1: $35$ points.
Subtask 2: $25$ points.
Subtask 3: $35$ points.
Subtask 4: $5$ points.

Examples1

Example 1

Input

4 5
1 2 -1 -4 -20
-8 -3 4 2 1
3 8 10 1 3
-4 -1 1 7 -6

Expected output