《Cracking the Coding Interview》——第18章:难题——题目12
2024-08-28 22:37:22
2014-04-29 04:36
题目:最大子数组和的二位扩展:最大子矩阵和。
解法:一个维度上进行枚举,复杂度O(n^2);另一个维度执行最大子数组和算法,复杂度O(n)。总体时间复杂度为O(n^3),还需要O(n)额外空间。
代码:
// 18.12 Given an n x n matrix, find the submatrix with largest sum. Return the sum as the result.
#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
using namespace std; class Solution {
public:
int largestSubmatrixSum (const vector<vector<int> > &matrix) {
n = matrix.size();
if (n == ) {
return ;
}
m = matrix[].size();
if (m == ) {
return ;
} int i, j, k;
vector<int> v;
int msum;
int sum; v.resize(m);
msum = INT_MIN;
for (i = ; i < n; ++i) {
fill(v.begin(), v.end(), );
for (j = i; j < n; ++j) {
for (k = ; k < m; ++k) {
v[k] += matrix[j][k];
}
sum = maxSubarraySum(v, m);
msum = max(msum, sum);
}
}
v.clear();
return msum;
};
private:
int n, m; int maxSubarraySum(const vector<int> &v, int n) {
int msum;
int sum;
int i; msum = INT_MIN;
for (i = ; i < n; ++i) {
if (v[i] >= ) {
msum = max(msum, v[i]);
break;
}
}
if (i == n) {
return msum;
} msum = sum = ;
for (i = ; i < n; ++i) {
sum += v[i];
msum = max(msum, sum);
sum = max(sum, );
} return msum;
};
}; int main()
{
int i, j;
int n, m;
vector<vector<int> > matrix;
Solution sol; while (cin >> n >> m && (n > && m > )) {
matrix.resize(n);
for (i = ; i < n; ++i) {
matrix[i].resize(m);
for (j = ; j < m; ++j) {
cin >> matrix[i][j];
}
}
cout << sol.largestSubmatrixSum(matrix) << endl; for (i = ; i < n; ++i) {
matrix[i].clear();
}
matrix.clear();
} return ;
}
最新文章
- HTML5新的标签和属性
- C#类和接口、虚方法和抽象方法及值类型和引用类型的区别
- Codeforces 546E Soldier and Traveling(最大流)
- WEB安全--CSRF防御
- eclipse js卡顿
- KSM剖析——Linux 内核中的内存去耦合
- Python内置数据类型之Tuple篇
- Linux下的vi编辑命令中查找&#183;替换详解
- Sevlet局部变量初始化
- TimeUnit
- Android笔记: 日期格式化
- CENTOS6.6 下mysql MHA架构搭建
- css常见属性
- 利用openxml在Excel中插入图表
- SWUST OJ(961)
- ccf--20140303--命令行选项
- html table标签
- 查找mac下腾讯视频下载地址
- RHEL7 -- NetworkManager
- winfrom 窗口起始位置为屏幕中央