【Leetcode 面试题 17.24. 最大子矩阵 (最大子数组和的二维版本）】
文章图片
1. 暴力做法枚举r1，c1, r2, c2，求和，时间复杂度O(N^6)很爆炸。
2. 优化方法，二维前缀和优化，O(1)时间内求出给定r1，c1，r2，c2区域的和，时间复杂度为O(N^4)
3. 降维动态规划优化。
文章图片
枚举起始行和结束行，对列求和，等效成一维最大子序列问题。由于所有起始行和结束行都枚举过，所以这个做法一定是对的。
这道题目还需要记录更新r1，c1，r2，c2比一般的题目要难。
class Solution {
public:
vector getMaxMatrix(vector>& matrix) {
int max = INT_MIN, n = matrix.size(), m = matrix[0].size();
int r1, c1, r2, c2;
for(int i=0;
i s(m);
for(int j=i;
j0) cur+=s[k];
else{
cur = s[k];
tmp = k;
}
if(cur>max){
max = cur;
r1 = i;
c1 = tmp;
r2 = j;
c2 = k;
}
}
}
}
return {r1,c1,r2,c2};
}
};
推荐阅读
- 人工智能|干货！人体姿态估计与运动预测
- 分析COMP122 The Caesar Cipher
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- Python机器学习基础与进阶|Python机器学习--集成学习算法--XGBoost算法
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- 人工智能|【机器学习】深度盘点（详细介绍 Python 中的 7 种交叉验证方法！）
- 网络|简单聊聊压缩网络