题目：
1、一个N个元素的一维数组，求该数组的最大子数组之和
2、求二维数组的最大子数组之和
题目1，思路：
使用start[i]表示包含元素i的子数组和的最大值，start[i]=max(array[i],start[i-1]+array[i])
使用all[i]表示元素i之前的最大子数组和，all[i]=max(start[i],all[i-1])
由于start[i]和all[i]的求解只需要用到上一次的值start[i-1]和all[i-1]，可以使用start和all表示
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 |
#include<iostream>using
namespace std;#define MAX(a,b) \ ((a)>(b)?(a):(b))int maxArray(int
array[],int
size){ int
start=array[0]; int
all=array[0]; int
end=0; int
length=0; for(int
i=1;i<size;i++) { start=MAX(array[i],start+array[i]); all=MAX(all,start); if(all==start) { end=i; if(start==array[i]) length=0; else length++; } } cout<<"sub index:["<<end-length<<","<<end<<"]"<<endl; return
all;}int
main(){ int
array[]={9,1,3,-10,16}; int
size=sizeof(array)/sizeof(int); cout<<"MaxArray:"<<maxArray(array,size)<<endl;} |
题目2，思路：
解法一：穷举法，枚举每一个矩形区域，求解这个矩形区域中元素的和。
解法二：降维法
如上图所示，把i行和j行之间的元素看成一个整体，将二维降低为一维求解最大子数组和。
步骤：
1、枚举上下边界i行和j行
2、使用一维的方法求解二维最大子数组和
#include<iostream> #include<limits.h> using namespace std; #define M 3 #define N 3 #define MAX(a,b)\ (a)>(b)?(a):(b) int p[M][N]; //p[i][j] indicate (0,0) to (i,j) matrix sum void init(int (*array)[N],int m,int n) { //init row for(int i=0;i<m;i++) { p[i][0]=p[i-1][0]+array[i][0]; } //init col for(int j=0;j<n;j++) { p[0][j]=p[0][j-1]+array[0][j]; } for(int i=1;i<m;i++) { for(int j=1;j<n;j++) { p[i][j]=p[i-1][j]+p[i][j-1]-p[i-1][j-1]+array[i][j]; } } } //sum row i and j with col k int Col_ij(int i,int j,int k) { int value=0; if(k==0) { if(i==0) value=p[j][k]; else value=p[j][k]-p[i-1][k]; } else { if(i==0) value=p[j][k]-p[j][k-1]; else value=p[j][k]-p[j][k-1]-p[i-1][k]+p[i-1][k-1]; } return value; } int maxArray(int (*array)[N],int m,int n) { int max=-1*INT_MAX; int rowi=0; int rowj=0; int coli=0; int colj=0; for(int i=0;i<m;i++) { for(int j=i;j<m;j++) { int start=Col_ij(i,j,0); int all=Col_ij(i,j,0); int end=0; int length=0; for(int k=1;k<n;k++) { int value=Col_ij(i,j,k); start=MAX(value,start+value); all=MAX(start,all); if(all==start) { end=k; if(start==value) length=0; else length++; } } if(all>max) { max=all; rowi=i; rowj=j; coli=end-length; colj=end; } } } cout<<"row:"<<"["<<rowi<<","<<rowj<<"]"<<endl; cout<<"col:"<<"["<<coli<<","<<colj<<"]"<<endl; return max; } int main() { int array[M][N]={ {-1,2,-3}, {-2,5,2}, {3,4,3} }; init(array,M,N); int max=maxArray(array,M,N); cout<<"max:"<<max<<endl; }
原文：http://www.cnblogs.com/luosongchao/p/3679395.html