题目
给定一个由N个整数元素组成的数组arr，数组中有正数也有负数，这个数组不是一般的数组，其首尾是相连的。数组中一个或多个连续元素可以组成一个子数组，其中存在这样的子数组arr[i],…arr[n-1],arr[0],…,arr[j]，现在请你这个ACM_Lover用一个最高效的方法帮忙找出所有连续子数组和的最大值（如果数组中的元素全部为负数，则最大和为0，即一个也没有选）。
输入：
输入包含多个测试用例，每个测试用例共有两行，第一行是一个整数n（1<=n<= 100000），表示数组的长度，第二行依次输入n个整数（整数绝对值不大于1000）。
输出：
对于每个测试用例，请输出子数组和的最大值。
样例输入：
6
1 -2 3 5 -1 2
5
6 -1 5 4 -7
样例输出：
10
14
思路一
与[LeetCode]53.Maximum Subarray题目相类似，唯一区别是本题是首尾相连，首尾相连的数组难点是到达尾部后继续从头开始，比类似题目稍微复杂些。
这里采用拉长数组的方法避免了这些问题：将数组平铺为一个长度为2倍原先长度的的新数组，这样问题就变成了：求一个整型数组中长度不超过len（原数组长度）的子数组和的最大值，降低了难度。
代码
/*---------------------------------------------
* 日期：2015-02-20
* 作者：SJF0115
* 题目: 求首尾相连数组的最大子数组和
* 来源：淘宝
* 博客：
-----------------------------------------------*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int MaxSubarray(int a[],int n){
if(n <= 0){
return 0;
}//if
int size = 2*n;
// 构造2倍长度数组
vector<int> num(a,a+n);
for(int i = 0;i < n;++i){
num.push_back(a[i]);
}//for
int max = 0;
int sum = 0,start = 0,end = 0;
for(int i = 0;i < size;++i){
sum += num[i];
if(sum < 0){
sum = 0;
start = i+1;
}//if
if(start >= n || (i - start + 1) > n){
break;
}//if
if(max < sum){
max = sum;
end = i;
}//if
}//for
cout<<"最大数组["<<start%n<<","<<end<<"]"<<endl;
return max;
}
};
int main() {
Solution solution;
int num[] = {-1,-5,-4,-7};
int result = solution.MaxSubarray(num,4);
cout<<result<<endl;
}思路二
可以把问题的解分为两种情况：
（1）解没有跨过A[n-1]到A[0]
（2）解跨过A[n-1]到A[0]
对于这种情况，只要找到从A[0]开始和最大的一段（A[0]…..A[j]）（0 <= j < n）
以及以A[n-1]结尾的和最大的一段（A[i]…..A[n-1]）（0 <= i < n）
该种情况的最大值为A[i]+…..+A[n-1]+A[0]+….+A[j]
如果i <= j 则最大值为A[0]+…..+A[n-1]否则最大值为A[i]+…..+A[n-1]+A[0]+….+A[j]
最后，取两种情况的最大值就可以了。求解跨过A[n-1]到A[0]的情况只需要遍历数组一次，故总的时间复杂度为O(N)+O(N) = O(N)
代码
/*---------------------------------------------
* 日期：2015-02-20
* 作者：SJF0115
* 题目: 求首尾相连数组的最大子数组和
* 来源：淘宝
* 博客：
-----------------------------------------------*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int MaxSubarray(int a[],int n){
if(n <= 0){
return 0;
}//if
int max = 0;
int sum = 0,start = 0;
// 第一种情况
for(int i = 0;i < n;++i){
sum += a[i];
if(sum < 0){
sum = 0;
start = i+1;
}//if
if((i - start + 1) > n){
break;
}//if
if(max < sum){
max = sum;
}//if
}//for
// 第二种情况
int sumLeft = 0,sumRight = 0;
int maxLeft = 0,maxRight = 0;
int left = 0,right = n-1;
// 以a[0]开头的最大连续和
for(int i = 0;i < n;i++){
sumLeft += a[i];
if(sumLeft < 0){
break;
}//if
if(maxLeft < sumLeft){
maxLeft = sumLeft;
left = i;
}//if
}//for
// 以a[n-1]结尾的最大连续和
for(int j = n-1;j >= 0;--j){
sumRight += a[j];
if(sumRight < 0){
break;
}//if
if(maxRight < sumRight){
maxRight = sumRight;
right = j;
}//if
}//for
if(left >= right){
return max;
}//if
return max > (maxLeft + maxRight)?max:(maxLeft+maxRight);
}
};
int main() {
Solution solution;
//int num[] = {1,-2,3,5,-1,2};
//int num[] = {6,-1,5,4,-7};
int num[] = {-1,-3,-4};
int result = solution.MaxSubarray(num,3);
cout<<result<<endl;
}