class Solution {
public:
vector<int> getMaxMatrix(vector<vector<int>>& matrix) {
}
};
面试题 17.24. 最大子矩阵
给定一个正整数、负整数和 0 组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。
返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。
注意：本题相对书上原题稍作改动
示例：
输入：
[
[-1,0],
[0,-1]
]
输出：[0,1,0,1]
解释：输入中标粗的元素即为输出所表示的矩阵
说明：
1 <= matrix.length, matrix[0].length <= 200原站题解
python3 解法, 执行用时: 1732 ms, 内存消耗: 17.2 MB, 提交时间: 2023-04-22 12:43:24
class Solution:
def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:
# 二维数组转变成一维数组求LIS
n=len(matrix)
m=len(matrix[0])
ans=[0]*4
# 定义数组求和,二维转一维
b=[0]*m
max_sum=matrix[0][0] # 初始化
r1=c1=0
for i in range(n):
b=[0]*m # 每次循环初始化b
for j in range(i,n):
sum = 0 # 定义dp[i]
for k in range(m):
b[k]+=matrix[j][k]
if sum>0:
sum+=b[k]
else:
sum=b[k] # 说明之前的和小于零需要舍弃，重新开始
r1=i
c1=k
if sum>max_sum:
max_sum=sum
ans[0]=r1
ans[1]=c1
ans[2]=j
ans[3]=k
return ans
python3 解法, 执行用时: 1804 ms, 内存消耗: 17.3 MB, 提交时间: 2023-04-22 12:42:38
class Solution:
#leetcode 363 代码套路一样
def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:
row = len(matrix)
col = len(matrix[0])
maxArea = float('-inf') #最大面积
res = [0, 0, 0, 0]
for left in range(col): #从左到右，从上到下，滚动遍历
colSum = [0] * row #以left为左边界，每行的总和
for right in range(left, col): #这一列每一位为右边界
for i in range(row): #遍历列中每一位，计算前缀和
colSum[i] += matrix[i][right]
startX, endX, maxAreaCur= self.getMax(colSum)#在left，right为边界下的矩阵中，前缀和colSum的最大值
if maxAreaCur > maxArea:
res = [startX, left, endX, right] #left是起点y轴坐标，right是终点y轴坐标
maxArea = maxAreaCur
return res
#这一列中，找最大值，同时记录起点，终点
#因为传进来的是列的前缀和，所以返回的起点、终点代表的是行坐标
def getMax(self, nums):
n = len(nums)
maxVal, curSum = nums[0], nums[0] #初始化最大值
startIndex, end, start = 0, 0, 0 #初始化临时起点，起点，终点
for i in range(1,n):
if curSum<0: #前缀和小于0了，前面就不要了，从当前开始
curSum = nums[i]
startIndex = i #前面的前缀和小于0了，需要重置起点，从当前开始才有可能成为最大值
else:
curSum = curSum + nums[i]
if curSum > maxVal:
maxVal = curSum
start = startIndex #记录下前面的起点，默认0，或者是curSum<0后，重新更新的起点
end = i #终点是当前坐标
return start, end, maxVal #起点，终点，最大前缀和（最大面积）
java 解法, 执行用时: 43 ms, 内存消耗: 46.8 MB, 提交时间: 2023-04-22 12:41:35
class Solution {
public int[] getMaxMatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
// 用于暂存矩阵的列和
int[] sum = new int[n];
int[] ans = new int[4];
int maxAns = matrix[0][0];
for(int i=0;i<m;i++){
// 重置列和
for(int t=0;t<n;t++) sum[t] = 0;
for(int j=i;j<m;j++){
// start 记录最大连续数组子序的开始位置
int maxSum = 0, start = 0;
for(int k=0;k<n;k++){
// sum[k] 表示 矩阵中 i ~ j 行 k 列元素的和
sum[k] += matrix[j][k];
// 动态规划求sum数组中最大的连续子序之和
if(maxSum > 0){
maxSum += sum[k];
}else{
maxSum = sum[k];
start = k;
}
if(maxSum > maxAns){
ans[0] = i; ans[1] = start;
ans[2] = j; ans[3] = k;
maxAns = maxSum;
}
}
}
}
return ans;
}
}
cpp 解法, 执行用时: 172 ms, 内存消耗: 12.4 MB, 提交时间: 2023-04-22 12:39:35
class Solution {
public:
vector<int> getMaxMatrix(vector<vector<int>>& matrix) {
vector<int> ans(4);//保存最大子矩阵的左上角和右下角的行列坐标
int N = matrix.size();
int M = matrix[0].size();
vector<int> b(M,0);//记录当前i~j行组成大矩阵的每一列的和，将二维转化为一维
int sum;//相当于dp[i],dp_i
int maxsum=INT_MIN;//记录最大值
int bestr1,bestc1;//暂时记录左上角，相当于begin
for(int i=0;i<N;i++){ //以i为上边，从上而下扫描
for(int t=0;t<M;t++ ) b[t]=0; //每次更换子矩形上边，就要清空b，重新计算每列的和
for(int j=i;j<N;j++){ //子矩阵的下边，从i到N-1，不断增加子矩阵的高
//一下就相当于求一次最大子序列和
sum = 0;//从头开始求dp
for(int k=0;k<M;k++){
b[k]+=matrix[j][k];
//我们只是不断增加其高，也就是下移矩阵下边，所有这个矩阵每列的和只需要加上新加的哪一行的元素
//因为我们求dp[i]的时候只需要dp[i-1]和nums[i],所有在我们不断更新b数组时就可以求出当前位置的dp_i
if(sum>0){
sum+=b[k];
}
else{
sum=b[k];
bestr1=i;//自立门户，暂时保存其左上角
bestc1=k;
}
if( sum > maxsum){
maxsum = sum;
ans[0]=bestr1;//更新答案
ans[1]=bestc1;
ans[2]=j;
ans[3]=k;
}
}
}
}
return ans;
}
};