LeetCode 面试题 17.24. 最大子矩阵**

可以看做最大连续子序列和的升级版；

想到了用前缀和，但是没有想到后续该怎么dp；

固定上边界和下边界，对一整行进行前缀和dp；

如果值为正，代表有增长的可能；

如果为负直接舍弃，因为对后面的增长毫无用处；

class Solution {
public:
    vector getMaxMatrix(vector>& matrix) {
        int m=matrix.size();
        int n=matrix[0].size();
        vector>dp(m+1,vector(n+1,0));
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+matrix[i-1][j-1];
            }
        }
        int len=min(m,n);
        int maxn=INT_MIN;
        vectorvec(4,-1);
        for(int top=0;top
            //上边界
            for(int low=top;low
                //下边界；
                int left=0,right=0;
                while(right
                    //坐标：top,left.  low,right;
                    int res=dp[low+1][right+1]+dp[top][left]-dp[low+1][left]-dp[top][right+1];
                    if(res>maxn){
                        maxn=res;
                        vec[0]=top;
                        vec[1]=left;
                        vec[2]=low;
                        vec[3]=right;
                    }
                    if(res<0){
                        left=right+1;
                    }
                    right++;
                }
            }
        }
        return vec;
    }
};