Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],

the contiguous subarray [4,-1,2,1] has the largest sum = 6.

解决方法：

已经有人提出了O（n）的解决方法，答题思路是，对于数组中第一个元素a[0]与最大的一段数组（a[i]```a[j]），有三种情况：

1.i=j=0,即a[0]为最大的一段；

2.0=i<j,和最大的一段以a[0]；

3.0<i,和最大的一段为（a[i]```a[j]）。

用递推方式解决问题。函数为类中的maxSubArray(vector<int>& nums)。

若用分形算法来做，可将a[0]```a[n-1]分成a[0]```a[(n-1)/2]和a((n+1)/2)```a[n-1]两部分，首先分别求出他们的和最大值max1,max2，整个数组的和最大值可能等于max(max1,max2),或者和最大子段跨越两个数组，分别求出第一段中以a[(n-1)/2]结尾的和最大值，第二段中以a((n+1)/2)为首的和最大值，令max3为他们的和，则整个数组的和最大值为max{max1,max2,max3}.

分形算法的复杂度为O（n log n)。函数为类中的maxSubArray1(vector<int>& nums).

完整的代码如下：

#include<iostream>#include<vector>#include<algorithm>#include<numeric>#include <math.h> using namespace std;class Solution {public:    int maxSubArray(vector<int>& nums);	int maxSubArray1(vector<int>& nums);};int Solution::maxSubArray(vector<int>& nums){	int x;	int i;		//while(cin>>x&&x!='p')//输入数组中元素，输入p为结束	//{	//	nums.push_back(x);	////	cin>>x;	//}	//	int t=nums.size();	int nstart=nums[t-1];	int nall=nums[t-1];			for(i=t-2;i>=0;i--)	{		if(nstart<0)			nstart=0;		nstart+=nums[i];		if(nstart>nall)			nall=nstart;	}	//cout<<nall<<endl;	return nall;}int Solution::maxSubArray1(vector<int>& nums){	//int w;	//	while(cin>>w&&w!='p')//输入数组中元素，输入p为结束	//{	//	nums.push_back(w);	////	cin>>x;	//}		int len=nums.size();	double l=((double)len)/2;	int t=ceil(l);	int x,y,z;	int sum1,sum2;	int max1,max2,max3;	if(len==1)		return nums[0];	else	{	vector<int>::iterator it1=nums.begin();	vector<int>::iterator it2=nums.begin()+t;	vector<int> nums1(it1,it2);	it1=nums.begin()+t;	it2=nums.end();	vector<int> nums2(it1,it2);	x=maxSubArray1(nums1);	y=maxSubArray1(nums2);	x=(x>y)?x:y;	max1=sum1=nums[t-1];	max2=sum2=nums[t];	for(int i=t-2;i>=0;i--)	{		sum1+=nums[i];		max1=(max1>sum1)?max1:sum1;	}	for(int i=t+1;i<len;i++)	{		sum2+=nums[i];		max2=(max2>sum2)?max2:sum2;	}	max3=max1+max2;	x=(x>max3)?x:max3;	//cout<<x<<endl;	return x;	}}		int main(){	vector<int> nums;	Solution s;	int w;		while(cin>>w&&w!='p')//输入数组中元素，输入p为结束	{		nums.push_back(w);	//	cin>>x;	}	cout<<s.maxSubArray1(nums)<<endl;	return 0;}