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 ;
}

最新文章

  1. HTML5新的标签和属性
  2. C#类和接口、虚方法和抽象方法及值类型和引用类型的区别
  3. Codeforces 546E Soldier and Traveling(最大流)
  4. WEB安全--CSRF防御
  5. eclipse js卡顿
  6. KSM剖析——Linux 内核中的内存去耦合
  7. Python内置数据类型之Tuple篇
  8. Linux下的vi编辑命令中查找&#183;替换详解
  9. Sevlet局部变量初始化
  10. TimeUnit
  11. Android笔记: 日期格式化
  12. CENTOS6.6 下mysql MHA架构搭建
  13. css常见属性
  14. 利用openxml在Excel中插入图表
  15. SWUST OJ(961)
  16. ccf--20140303--命令行选项
  17. html table标签
  18. 查找mac下腾讯视频下载地址
  19. RHEL7 -- NetworkManager
  20. winfrom 窗口起始位置为屏幕中央

热门文章

  1. COGS 2075. [ZLXOI2015][异次元圣战III]ZLX的陨落
  2. java 内存举例
  3. jQuery UI datepicker z-index默认为1 怎么处理
  4. 移除input number上的spinner
  5. C#在派生类中调用基类成员
  6. Hive[6] HiveQL 查询
  7. ES6初识-模块化
  8. UVA_1434_YAPTCHA
  9. Wordpress网站中添加百度统计代码
  10. JDK5 新特性