设计思路：
只需要将一维数组循环两边，从中求出最大子数组之和。
将这个一维数组扩大两倍，在这个一维数组后，继续跟上该一维数组。
由于是一个圈，所以数组长度不变，只需要限制循环次数便可。
出现的问题：
在求最大子数组过程中，限制循环次数。如果只是简单的限制循环N次（N为数组长度），有些数据就会出现错误的情况。
考虑到end1[j1-1] - j2 > N来判断最大子数组长度，但是没有考虑大求得的最大值应该与end[j1-1]同步。
源代码：
1 //XiaoSong Du 2015/4//11 2 #include <iostream> 3 #include <time.h> 4 using namespace std; 5 #define N 10 6 7 void main() 8 { 9 int a[2*N],d = 0,d1 = 0; 10 int maxd[2*N]={0} ,end2 = 0,end1[2*N]={0}; 11 int j = -1,j1 = 0,j2 = -1;//j记录正整数前负数下标，j2记录最大数组之和前的负数下标 12 srand((unsigned int)time(0)); 13 14 for (int i = 0;i < N;i++) 15 { 16 a[i] = rand()%50 - 25; 17 a[i+N] = a[i]; 18 } 19 for (int i = 0;i < N;i++) 20 { 21 cout << a[i] << " "; 22 } 23 cout << endl; 24 25 maxd[j1] = a[0]; 26 for (int i = 0;i < 2*N;i++) 27 { 28 d += a[i]; 29 if (d > maxd[j1-1]) 30 { 31 maxd[j1] = d; 32 end1[j1] = i; 33 j1++; 34 j2 = j; 35 } 36 if(d < 0) 37 { 38 d = 0; 39 j = i; 40 } 41 42 if (end1[j1-1] - j2 > N) //如果end1[j1-1] - j2大于N个数，那么就获取end1[j1-2] 43 { 44 j1--; 45 break; 46 } 47 } 48 cout << endl; 49 end2 = j2+1; 50 51 cout << "最大子数组是：由"; 52 for (int i = end2;i <= end1[j1-1];i++) 53 { 54 if (i > N-1) 55 { 56 cout << "第" << i+1 -N << " "; 57 } 58 else 59 { 60 cout << "第" << i+1 << " "; 61 } 62 } 63 cout << ",这些数组成。" << endl; 64 cout << endl; 65 cout << "子数组为："; 66 for (int i = end2;i <= end1[j1-1];i++) 67 cout << a[i] << " "; 68 cout << endl; 69 cout << "和为： " << maxd[j1-1] << endl; 70 }
运行结果截图：
总结：
在做位置定位的时候，位置下标一直出问题。如果用每次循环N个数（N为数组长度），时间复杂度便需要O（n^2），不满意，舍去。所以在求最大子数组过程中，加上条件限制，当出现最大子数组时，长度最大为N。问题因此而解决。不过想法出来了，可是在做的过程中还是出现问题。不断试验，更改代码，用了一上午的时间终于解决了。算法比以前更加简练，但是时间复杂度仍为O（n）。
团队照片：
