leetcode 363. Max Sum of Rectangle No Larger Than K 子矩形和小于K的最大值 + 动态规划DP + 暴力循环真好

爱被打了一巴掌 2022-06-07 02:45 79阅读 0赞

Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k.

Example:  
Given matrix = \[  
\[1, 0, 1\],  
\[0, -2, 3\]  
\]  
k = 2  
The answer is 2. Because the sum of rectangle \[\[0, 1\], \[-2, 3\]\] is 2 and 2 is the max number no larger than k (k = 2).

Note:  
The rectangle inside the matrix must have an area > 0.  
What if the number of rows is much larger than the number of columns?

没有想到更好地做法，我这里直接暴力求解。效果还不错，accept了。

代码如下：

import java.util.TreeSet;
    
    
    class Solution 
    {
        /*
         * 暴力做法很定不好，但是暂时想不到更好的办法，所以先这么办吧
         * */
        public int maxSumSubmatrix(int[][] matrix, int k) 
        {
            if(matrix==null || matrix.length<=0)
                return 0;
    
            int[][] sum=new int[matrix.length+1][matrix[0].length+1];       
            for(int i=1;i<=matrix.length;i++)
                for(int j=1;j<=matrix[0].length;j++)
                    sum[i][j]=matrix[i-1][j-1]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
    
            int max=Integer.MIN_VALUE;
            for(int i=1;i<=matrix.length;i++)
            {
                for(int j=1;j<=matrix[0].length;j++)
                {
                    for(int g=0;g<i;g++)
                    {
                        for(int h=0;h<j;h++)
                        {
                            int one=sum[i][j]-(sum[i][h]+sum[g][j]-sum[g][h]);
                            if(one<=k)
                                max = Math.max(max, one);
                        }
                    }
                }
            }
            return max;
        }
    }

下面就是C++的做法

就是一个DP来求解矩形面积，然后遍历暴力求解即可，

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
        int maxSumSubmatrix(vector<vector<int>>& mat, int k)
        {
            if (mat.size() <= 0)
                return 0;
            int row = mat.size(), col = mat[0].size();
            vector<vector<int>> dp(row + 1, vector<int>(col + 1, 0));
            for (int i = 1; i <= row; i++)
            {
                for (int j = 1; j <= col; j++)
                {
                    dp[i][j] = mat[i-1][j-1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
                }
            }
    
            int res = INT_MIN;
            for (int i = 1; i <= row; i++)
            {
                for (int j = 1; j <= col; j++)
                {
                    for (int ii = 0; ii < i; ii++)
                    {
                        for (int jj = 0; jj < j; jj++)
                        {
                            int one = dp[i][j] - dp[ii][j] - dp[i][jj] + dp[ii][jj];
                            if(one<=k)
                                res = max(res, one);
                        }
                    }
                }
            }
            return res;
        }
    };