[经典面试题][淘宝]求首尾相连数组的最大子数组和

题目

给定一个由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* 题目: 求首尾相连数组的最大子数组和* 来源：淘宝* 博客：———————————————–*/;class Solution {public:int MaxSubarray(int a[],int n){if(n <= 0){return 0;}//ifint size = 2*n;// 构造2倍长度数组vector<int> num(a,a+n);for(int i = 0;i < n;++i){num.push_back(a[i]);}//forint 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;}//ifif(start >= n || (i – start + 1) > n){break;}//ifif(max < sum){max = sum;end = i;}//if}//forcout<<“最大数组[“<<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* 题目: 求首尾相连数组的最大子数组和* 来源：淘宝* 博客：———————————————–*/using namespace std;:int MaxSubarray(int a[],int n){if(n <= 0){return 0;}//ifint 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;}//ifif((i – start + 1) > n){break;}//ifif(max < sum){max = sum;}//if}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;}//ifif(maxLeft < sumLeft){maxLeft = sumLeft;left = i;}//if}(int j = n-1;j >= 0;–j){sumRight += a[j];if(sumRight < 0){break;}//ifif(maxRight < sumRight){maxRight = sumRight;right = j;}//if}//forif(left >= right){return max;}//ifreturn max > (maxLeft + maxRight)?max:(maxLeft+maxRight);}};int main() {Solution solution;num[] = {-1,-3,-4};int result = solution.MaxSubarray(num,3);cout<<result<<endl;}

看了哪些风景，遇到哪些人。尽管同学说，去旅行不在于记忆，