算法1 dp求最大子矩阵算法

可以过一部分，另一些答案错误。

const int N = 110;

class Solution {
public:

    vector<vector<int>> p;
    int m, n;
    int total[N][N];
    int arr[N];
    int dp[N];

    int getMaxSequence(int key){
        int maxn = -100001;
        for(int i = 0; i < n; i++){
            if(i == 0){
                dp[i] = arr[i];
            }else{
                if(arr[i] > key){
                    dp[i] = dp[i-1]+arr[i];
                }else if(dp[i-1]+arr[i] > key){
                    dp[i] = arr[i];
                }else{
                    dp[i] = max(arr[i], dp[i-1]+arr[i]);
                } 
            }
            if(arr[i] == -128 || dp[i] == -128) printf("yes\n");
            //printf("%d\n", dp[i]);
            if(dp[i] <= key){
                maxn = max(maxn, dp[i]);
                //printf("%d\n", maxn);
            }
        }
        return maxn;
    }

    int getMaxMatrix(int key){
        int maxn = -100001, tmp;
        for(int i = 0; i < m; i++){
            for(int j = i; j < m; j++){
                for(int k = 0; k < n; k++){
                    if(i == 0){
                        arr[k] = total[j][k];
                    }else{
                        arr[k] = total[j][k] - total[i-1][k];
                    }
                    if(arr[i] == -128) printf("yes\n");
                    //printf("arr %d = %d\n", k, arr[k]);
                }
                tmp = getMaxSequence(key);
                //if(i > 6) printf("i = %d j = %d, tmp = %d\n",i, j, tmp);
                maxn = max(maxn, tmp);
            }
        }
        return maxn;
    }

    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        p = matrix;
        m = matrix.size();
        n = matrix[0].size();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(i == 0){
                    total[i][j] = matrix[i][j];
                }else{
                    total[i][j] = total[i-1][j] + matrix[i][j];
                }
            }
        }
        int ans = getMaxMatrix(k);
        return ans;
    }
};

算法2

修改了getmaxsequence函数，通过。说明之前遍历有地方没有考虑到。

参考
https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/solution/czhuang-tai-ya-suo-dong-tai-gui-hua-by-cainhsu/

const int N = 110;

class Solution {
public:

    vector<vector<int>> p;
    int m, n;
    int total[N][N];
    int arr[N];
    int dp[N];

    int getMaxSequence(int key){
        int cur;
        int ans = INT_MIN;
        for(int i = 0; i < n; i++){
            cur = 0;
            for(int j = i; j < n; j++){
                cur += arr[j];
                if(cur <= key){
                    ans = max(ans, cur);
                    if(ans == key) return ans;
                }
            }
        }
        return ans;
    }

    int getMaxMatrix(int key){
        int maxn = -100001, tmp;
        for(int i = 0; i < m; i++){
            for(int j = i; j < m; j++){
                for(int k = 0; k < n; k++){
                    if(i == 0){
                        arr[k] = total[j][k];
                    }else{
                        arr[k] = total[j][k] - total[i-1][k];
                    }
                    //printf("arr %d = %d\n", k, arr[k]);
                }
                tmp = getMaxSequence(key);
                //if(i > 6) printf("i = %d j = %d, tmp = %d\n",i, j, tmp);
                maxn = max(maxn, tmp);
            }
        }
        return maxn;
    }

    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        p = matrix;
        m = matrix.size();
        n = matrix[0].size();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(i == 0){
                    total[i][j] = matrix[i][j];
                }else{
                    total[i][j] = total[i-1][j] + matrix[i][j];
                }
                //if(matrix[i][j] == -128) printf("yes\n");
            }

        }
        int ans = getMaxMatrix(k);
        return ans;
    }
};

算法3

前缀和算法

参考老师的写的。正常循环x1,x2,y1,y2的时间复杂度是O(n4)，这个题目控制在O(n3logn)就行。
所以这里for循环 x1,x2,y2，剩下的y1用set和它的lower_bound。这个我之前不怎么熟悉。

lower_bound在set中用法：
二分查找一个有序数列，返回第一个大于等于x的数，如果没找到，返回末尾的迭代器位置

const int N = 110;

class Solution {
public:

    int m, n;
    int s[N][N];

    int getSum(int x1, int y1, int x2, int y2){
        return s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
    }

    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        m = matrix.size();
        n = matrix[0].size();

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + matrix[i-1][j-1];
            }
        }
        int ans = INT_MIN;
        for(int x1 = 1; x1 <= m; x1++){
            for(int x2 = x1; x2 <= m; x2++){
                set<int> S;
                S.insert(0);
                for(int y2 = 1; y2 <= n; y2++){
                    int si = getSum(x1, 1, x2, y2);
                    auto it = S.lower_bound(si-k);
                    if(it != S.end()) ans = max(ans, si - *it);
                    S.insert(si);
                }
            }
        }
        return ans;
    }
};