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;
}