首页 > 代码库 > 二位数组的子数组最大值
二位数组的子数组最大值
该题是poj的1050号题:http://poj.org/problem?id=1050
同时在《编程之美》 2.15 小节
思想是:
1、把二维降到一维,把 同一列的若干个数的和算出来,
然后从行的角度,变成求一维数组的子数组和的最大值,
一共要计算 (1+n)*n/2 次一维数组的和最大值
2、在求同一列的若干数的和的时候,用辅助数组加快计算:
把第l列中, 第1~k行数的和提前计算好,放到辅助数组 b[k][l]中,
然后求 第l列的 第i行和第j行之间的数的和,就等于 b[i][l]-b[j-1][l]
为了计算方便,第0行、0列都不存实际数,初始化为0。
#include <iostream> using namespace std; int a[101][101]; int b[101][101]; int MAX = -128; int max_two (int x, int y) { return x>y ? x : y; } int main () { int n; cin >> n; for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { cin >> a[i][j]; } } for(int i=0; i<=n; i++) { b[0][i] = 0; } for(int l=1; l<=n; l++) { for(int i=1; i<=n; i++) { b[i][l] = 0; for(int j=1; j<=i; j++) { b[i][l] += a[j][l]; } } } for (int i=1; i<=n; i++) { for (int j=i; j>=1; j--) { int all = b[i][n] - b[j-1][n]; int start = all; for (int k=n-1; k>=1; k--) { start = max_two(b[i][k]-b[j-1][k], start+b[i][k]-b[j-1][k]); all = max_two(all, start); } MAX = max_two(MAX, all); } } cout << MAX << endl; }
二位数组的子数组最大值
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。