1 //XiaoSong Du 2015/4/8 2 #include <iostream> 3 #include <time.h> 4 using namespace std; 5 #define M 3 6 #define N 6 7 8 void main() 9 { 10 int a[M][N],b[N],d = 0,d1 = 0; 11 int maxd ,maxd1,end1[M][N] = {0},end2[M][N] = {0}; 12 int i_max = 0,j_max = 0; 13 14 srand((unsigned int)time(0)); 15 16 for (int j = 0;j < M;j++) 17 { 18 for (int k = 0;k < N;k++) 19 { 20 a[j][k] = rand()%50 - 25; 21 cout << a[j][k] << " "; 22 } 23 cout << endl; 24 } 25 cout << endl; 26 27 maxd = a[0][0]; 28 maxd1 = a[0][0]; 29 for (int i = 0;i < M;i++)//i为0，表示1行，i为1表示两行数··· 30 { 31 for (int i_hang = 0;i_hang < M-i;i_hang++)//当1行是循环3次 32 { 33 for (int j = 0;j < N;j++)//赋初值 34 { 35 b[j] = 0; 36 } 37 for (int i_hang1 = i_hang;i_hang1 <= i_hang+i;i_hang1++)//每次循环i次赋值 38 { 39 for (int j = 0;j < N;j++) 40 { 41 b[j] += a[i_hang1][j]; 42 } 43 } 44 d = 0; 45 for (int k = 0;k < N;k++) 46 { 47 d += b[k]; 48 if (d > maxd) 49 { 50 maxd = d; 51 end1[i][i_hang] = k; 52 i_max = i; //最大的时候是i行； 53 j_max = i_hang; // 54 } 55 if(d < 0) 56 { 57 d = 0; 58 } 59 } 60 61 for (int k = N-1;k >= 0;k--) 62 { 63 d1 += b[k]; 64 if (d1 > maxd1) 65 { 66 maxd1 = d1; 67 end2[i][i_hang] = k; 68 } 69 if(d1 < 0) 70 { 71 d1 = 0; 72 } 73 } 74 75 } 76 } 77 cout << "子数组为：" << endl; 78 for (int k = 0;k <= i_max;k++) 79 { 80 for (int k1 = end2[i_max][j_max];k1 <= end1[i_max][j_max];k1++) 81 { 82 cout << a[j_max+k][k1] << " "; 83 } 84 cout << endl; 85 } 86 87 cout << endl; 88 cout << "和为： " << maxd << endl; 89 }
设计思路：
使用了一位数组求最大子数组之和的算法。在此基础上，先求出只有一行的最大子数组之和，然后将二维数组每一行最大子数组之和相比较，得到最大值。然后求每相邻两行的最大子数组之和，首先将相邻两行，同列相加，变成一个一维数组，从而求出最大子数组之和。求得之值与之前每一行最大子数组之和的结果相比。然后继续求相邻三行以此类推。最终求得二维数组最大子数组之和。
总结：
这个题目说难不难，说容易也不容易。由于采用了之前一维数组最大子数组之和的算法，所以很快就可以做出来。不过时间复杂度为O（n^3）。之后就是考虑如何才能化简，可是最终也没想到怎样办法。由于要便利一边二维数组，所以不可能为O(n)。但是O(n^2)目前自己也无法实现。
运算结果截图：
合作照片：
