1.题目：
返回一个二维整数数组中最大子数组的和。
2.要求：
输入一个二维整形数组，数组里有正数也有负数。
二维数组首尾相接，象个一条首尾相接带子一样。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
3.设计思路：
分别求出每一行的最大子矩阵，然后再两行相加，求出最大子矩阵，一直到所有的行相加，求出最大子矩阵。比较其中最大的子矩阵值，找出最大的。
4.源代码：
1 #include<iostream> 2 using namespace std; 3 #include <ctime> 4 #include <cstdlib> 5 #define MAX 10000 6 int Max(int b[]) 7 { 8 int m[MAX],n=0,p=0; 9 for(int i=0;i<4;i++) 10 { 11 for(int j=0;j<4;j++) 12 { 13 n=n+b[i+j]; 14 m[p]=n; 15 p++; 16 } 17 n=0; 18 } 19 int max=m[0]; 20 for(i=0;i<p;i++) 21 { 22 if(m[i]>max) 23 max=m[i]; 24 } 25 return max; 26 } 27 28 int main() 29 { 30 int k[MAX],a[4][8],h[8]; 31 srand(time(0)); 32 cout<<"该矩阵为:"<<endl; 33 for(int i=0;i<4;i++) 34 { 35 for(int j=0;j<4;j++) 36 { 37 a[i][j]=rand()%100-50; 38 a[i][j+4]=a[i][j]; 39 cout<<a[i][j]<<" "; 40 } 41 cout<<endl; 42 } 43 for(i=0;i<4;i++) 44 { 45 k[i]=Max(a[i]); 46 } 47 int q=4; 48 for(i=0;i<3;i++) 49 { 50 int t=0; 51 for(int j=0;j<8;j++) 52 { 53 54 h[t]=a[i][j]+a[i+1][j]; 55 t++; 56 } 57 k[q]=Max(h); 58 q++; 59 } 60 for(i=0;i<2;i++) 61 { 62 int t=0; 63 for(int j=0;j<8;j++) 64 { 65 66 h[t]=a[i][j]+a[i+1][j]+a[i+2][j]; 67 t++; 68 } 69 k[q]=Max(h); 70 q++; 71 } 72 int t=0; 73 i=0; 74 for(int j=0;j<8;j++) 75 { 76 77 h[t]=a[i][j]+a[i+1][j]+a[i+2][j]+a[i+3][j]; 78 t++; 79 } 80 k[q]=Max(h); 81 q++; 82 cout<<endl; 83 int max=k[0]; 84 for(i=0;i<q;i++) 85 { 86 if(k[i]>max) 87 max=k[i]; 88 } 89 cout<<"最大子矩阵的值为:"<<endl; 90 cout<<max; 91 return 0; 92 }
5.结果截图：
6.心得体会：
一次次的程序延伸，一次次的修改代码，让我们组对于子数组求和的理解更深了，但题目千变万化，我们还是要多多学习的，争取做到再难再复杂的变化也能攻破吧。