Problem Description

Bull version

The size of a known matrix is ​​​​defined as the sum of all elements in the matrix. Given a matrix, your task is to find the largest non-empty (at least of size 1*1) submatrix. For example, the largest submatrix of the following 4 * 4 matrix 0 - 2 - 7 0 9 2 - 6 2 - 4 1 - 4 1 - 1 8 0 - 2 is 9 2 - 4 1 - 1 8. The size of this submatrix is 15

Enter description:

The input is an N*N matrix. The first line of input gives N (0 < N <= 100). In the following lines, in turn (first give the N integers in the first row from left to right, then give the N integers in the second row from left to right...) give the N2 integers in the matrix, Integers are separated by whitespace characters (spaces or blank lines). It is known that the integers in the matrix are in the range [-127, 127].

Output description:

Output the size of the largest submatrix.

input sample

4
0 -2 -7 0
9 2 -6 2
-4 1 -4  1
-1 8  0 -2

Sample output

15

Click version

Given an N × M matrix of positive integers, negative integers, and 0s, write code to find the submatrix with the largest sum of elements. Returns an array [r1, c1, r2, c2], where r1, c1 represent the row and column numbers in the upper left corner of the submatrix, respectively, and r2, c2 represent the row and column numbers in the lower right corner, respectively. If there are multiple submatrices that satisfy the condition, any one can be returned. Note: This question is slightly modified from the original title in the book

Sample

enter:
[
   [-1,0],
   [0,-1]
]
output:[0,1,0,1]
Explanation: The bold element in the input is the matrix represented by the output

enter:
[
	[9,-8,1,3,-2],
	[-3,7,6,-2,4],
	[6,-4,-4,8,-7]
]
output:[0,0,2,3]

problem analysis

First of all, clarify the problem-solving method. Since the sub-problems are obviously related, the direct violent enumeration will inevitably time out under this amount of data. There is no obvious greedy element, and the sub-problems are related. Consider dynamic programming.

Secondly, consider the nature of the problem. This problem is a variant of the maximum sum of consecutive subarrays, and it is a dimension-raising version of subarrays. Therefore, we can consider how to use one-dimensional to assist in solving the current two-dimensional situation.

Considering the required elements, in order to get the sum quickly and avoid calculating the value multiple times during the operation, use the prefix sum array as an auxiliary.

Finally consider how to enumerate all cases. A solution, the matrix mentioned in the title, requires at least four parameters if it can be determined. It can be the subscript of the first point, the size of the matrix; or the subscript of the first point and the last point; or the first row, the last row, the first column, and the last column.

In order to facilitate the enumeration, we take the way of enumerating the first row, the last row, the first column, and the last column. At the same time, it traverses with the body of the row, enumerating the values ​​of different columns.

Since the minimum matrix can be 1*1, the first row and the last row can be equal. Similarly, the first and last columns can be the same.

We use i as the first row and j as the last row. From the meaning of the title, 0 <= i <= j< n .

So how to enumerate the columns?

If we compress the values ​​of the same column from row i to row j to one value at this time, then this problem is actually transformed into a one-dimensional continuous subarray maximum sum problem. A similar method can be used to solve the problem to obtain the starting and ending subscripts of the maximum sequence.

The specific programming details are not repeated here.

Since the title of the Niuke version is the specialization of the Likou version, (the Niuke input matrix is ​​n * n, and the Likou is n * m), so please refer to the Likou version for more codes.

code

/*Bull version*/
#include <cstdio>
#include <cstring>
int a[101][101];
int sum[101];
int n;
int main () {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            scanf("%d", &a[i][j]);
        }
    }
    
    int maxN = -32767;
    //Enumerate from line 0
    for(int i = 0; i < n; ++i) {
        memset(sum, 0, sizeof(sum));//Prefix and array set to 0
        for(int j = i; j < n; ++j) {
            int tmp = 0;
            for(int k = 0; k < n; ++k) {
                sum[k] += a[j][k];//Calculate the prefix sum of the current column
                tmp += sum[k];
                if(maxN < tmp) {
                    maxN = tmp;
                }
                if(tmp < 0) {
                    tmp = 0;
                }
            }
        }
    }
    printf("%d", maxN);
    return 0;
}

//leetcode version more general version
    vector<int> getMaxMatrix(vector<vector<int>>& matrix) {
        vector<int> ans;
        int n = matrix.size(), m = matrix[0].size();
        int maxN = INT_MIN, tmp, begin;
        vector<int> sum(m);
        for(int i = 0; i < n; ++i) {
            for(int &v:sum) v = 0;
            for(int j = i; j < n; ++j) {
                tmp = 0;
                begin = 0;
                for(int k = 0; k < m; ++k) {
                    sum[k] += matrix[j][k];
                    tmp += sum[k];
                    if(maxN < tmp) {
                        //cout << tmp << endl;
                        maxN = tmp;
                        ans = vector<int>{i, begin, j, k};
                    }
                    if(tmp < 0) {
                        tmp = 0;
                        begin = k + 1;
                    }
                }
            }
        }
        //cout << maxN << endl;
        return ans;
    }