题目描述：

给定一个由N个整数元素组成的数组arr，数组中有正数也有负数，这个数组不是一般的数组，其首尾是相连的。数组中一个或多个连续元素可以组成一个子数组，其中存在这样的子数组arr[i],…arr[n-1],arr[0],…,arr[j]，现在请你这个ACM_Lover用一个最高效的方法帮忙找出所有连续子数组和的最大值（如果数组中的元素全部为负数，则最大和为0，即一个也没有选）。

 

输入：

输入包含多个测试用例，每个测试用例共有两行，第一行是一个整数n（1=<n<=100000），表示数组的长度，第二行依次输入n个整数（整数绝对值不大于1000）。

 

输出：

对于每个测试用例，请输出子数组和的最大值。

 

样例输入：

61 -2 3 5 -1 256 -1 5 4 -7

样例输出：

1014
这种题很有做的价值，乍一看不难，但做下去却不知道如何下手。
一开始的思路是按每一个负数作为开头算一遍，超时了
后来想到题目其实是要找到一个开头点，使得这个开头点开始算出的子数组和最小，
那么，这个开头点是不是就是这个数组中最小的那个负数？
按这样编码，提交，答案错误

举个反例
6
-7 8 -6 2 -6 8

-7是最小的，但-6+2-6比-7 还要小
所以应该先在数组中找最小和子数组，但这样不就又变成原来的问题了吗？（从该数组之中任意一位开始去求，均可求出答案）
这时我们可以这样考虑这个问题，若这个最小和数组不涉及循环的问题，那么可以按一般方法求出，之后再以该数组末尾的下一个开始求最大和
若这个最小和数组存在于首尾相连的位置，那么我们如果从开始去求最大和（就是从数组中间求），即可求得答案。
代码如下

 1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <iostream> 5 using namespace std; 6 int num0[100002]; 7 int num[100002]; 8   9 int n;10  11 int find(int start) {12     int maxi = 0;13     int cnt = 0;14     for(int i = start; i < n; i++) {15         if(cnt < 0) {16             cnt = num[i];17         }18         else {19             cnt = cnt + num[i];20         }21         if(cnt > maxi) {22             maxi = cnt;23         }24     }25     for(int i = 0; i < start; i++) {26         if(cnt < 0) {27             cnt = num[i];28         }29         else {30             cnt = cnt + num[i];31         }32         if(cnt > maxi) {33             maxi = cnt;34         }35     }36     return maxi;37 }38 int main(int argc, char const *argv[])39 {40     while(scanf("%d",&n) != EOF) {41         int j = 0;42         memset(num, 0, sizeof(num));43         int state = 0;44         for(int i = 0; i < n; i++) {45             scanf("%d",&num0[i]);46             if(num0[i] > 0) {47                 if(state == 1) {48                     j++;49                     state = 0;50                 }51                 num[j++] = num0[i];52                  53             }54             else {55                 num[j] = num[j] + num0[i];56                 if(state == 0) {57                     state = 1;58                 }59                  60             }61         }62         n = j + state;63  64         /*for(int i = 0; i < n; i++) {65             printf("%d ",num[i]);66         }67         puts("");*/68         int local = 1002, global = 1002;69         int mini = -1;70         int sumi = 0;71         for(int i = 0; i < n; i++) {72             local = min(local+num[i], num[i]);73             if(local < global) {74                 mini = i;75                 global = local;76             }77         }78         int maxa = find(0);79         int maxt = find(mini);80         if(maxa < maxt) {81             maxa = maxt;82         }83         printf("%d\n",maxa);84     }   85     return 0;86 }

 

九度oj 题目1527：首尾相连数组的最大子数组和