求数组最大子数组之和

要求：

　　1.输入一个二维整形数组，数组里有正数也有负数。

　　2.二维数组中连续的一个子矩阵组成一个子数组，每个子数组都有一个和。

　　3.求所有子数组的和的最大值。要求时间复杂度为O(n)。

结对编程要求：

　　1.两人结对完成编程任务。

　　2. 一人主要负责程序分析，代码编程。 一人负责代码复审和代码测试计划。

　　3.发表一篇博客文章讲述两人合作中的过程、体会以及如何解决冲突(附结对开发的工作照)。

1 #include <iostream> 
2 using namespace std;
3 #define M 1000 
4 int A[M][M]; 
5 int AS[M][M]; 
6 inline int ArraySum(int s,int t,int i,int j)//定义求数组部分和函数 
7 { 
8 return AS[i][j]-AS[i][t-1]-AS[s-1][j]+AS[s-1][t-1]; 
9 } 
10 int max(int a,int b) 
11 { 
12 return(a>b?a:b); 
13 } 
14 int main() 
15 { 
16 int m,n,i,j; 
17 cout<<"请输入数组的行:"; 
18 cin>>n; 
19 cout<<"请输入数组的列:"; 
20 cin>>m; 
21 cout<<"请输入一个数组:"<<endl; 
22 for(i=0;i<n;i++) 
23 { 
24 for(j=0;j<m;j++) 
25 { 
26 cin>>A[i][j]; 
27 } 
28 } 
29 // 计算数组的部分和 
30 for(i=0;i<n;i++)//以(0,0)为定点一直到(i,j)求部分和 
31 { 
32 for(j=0;j<m;j++) 
33 { 
34 AS[i][j]=A[i][j]+AS[i-1][j]+AS[i][j-1]-AS[i-1][j-1]; 
35 } 
36 } 
37 int Max=A[0][0]; 
38 for(int a=0;a<n;a++) 
39 { 
40 for(int c=a;c<n;c++) 
41 { 
42 // 将子数组上下边界设为第a行和第c行，在这些子数组中取最大值 
43 int IV=ArraySum(a,0,c,0); 
44 for(j=1;j<m;j++) 
45 { 
46 IV=max(ArraySum(a,j,c,j),ArraySum(a,j,c,j)+IV); 
47 Max=max(IV,Max); 
48 } 
49 } 
50 } 
51 cout<<"数组最大子数组之和为:"<<Max<<endl; 
52 }

截图：

        

总结：

仔细学习了数组相关知识，思考了如何进行最大子数组的判断，并且与同学相互讨论增加自己的思考范围，最后得出这个算法。