问题描述

   给定（可能是负的）整数序列A1, A2,...,AN, 寻找（并标识）使Sum(Ak)(k >=i, k <= j)的值最大的序列。如果所有的整数都是负的，那么连续子序列的最大和是那个最大的负数项。最好给出给出最大和连续子序列！！

1 暴力破解法

这个问题有一个最简单直接的穷举解决法。我们看问题，既然要求里面最大的连续子序列。那么所有的连续子序列将由哪些组成呢？以数组的第一个元素为例，连续子序列必须是至少包含元素A1,也可能包含从A1到A2...以及从A1到AN。这样就有N种可能。后面的元素也按照这样类似的办法，以该元素开始，包含该元素的单元素数组，两个元素数组...直到包含数组末尾的数组。

#include <iostream>
#include <cstdlib>
#include <vector>

using namespace std;

int main()
{	
	vector<int> array;
	for(int i=0;i<20;i++)
	{
		int j = 50-random()%100; //-49~50
		array.push_back(j);
	}

	for(vector<int>::iterator it=array.begin();it!=array.end();++it)
	{
		cout<<*it<<" ";
	}
	cout<<endl;
	int maxsum=-50; //注意初始化
	int low=0;
       int high=0;
	for(int i=0;i<array.size();i++)
	{
		int sum=0;
		
		for(int j=i;j<array.size();j++)
		{
			sum+=array[j];
			if(sum>maxsum)
			{
				maxsum=sum;
				low=i;
				high=j;	
			}	
		}
	}
	cout<<"subarray:"<<array[low]<<"~"<<array[high]<<endl;
	cout<<"maxsun="<<maxsum<<endl;
return 0;
}

时间复杂度分析：两重循环遍历，复杂度为O（n^2）

2 分治策略（递归法）

对这个问题，有一个相对复杂的O(NlogN)的解法，就是使用递归。如果要是求出序列的位置的话，这将是最好的算法了（因为我们后面还会有个O(N)的算法，但是不能求出最大子序列的位置）。该方法我们采用“分治策略”（divide-and-conquer）。


在我们例子中，最大子序列可能在三个地方出现，或者在左半部，或者在右半部，或者跨越输入数据的中部而占据左右两部分。前两种情况递归求解，第三种情况的最大和可以通过求出前半部分最大和（包含前半部分最后一个元素）以及后半部分最大和（包含后半部分的第一个元素）相加而得到。

#include <iostream>
#include <cstdlib>
#include <vector>

using namespace std;
/*
* find a subarray crossing the mid with the biggist sum
*/

int find_max_crossing_subarray(vector<int> array,int low, int mid, int high)
{
    int left_maxsum=-50; //for sum
    int right_maxsum=-50; //for sum
    int sum =0;
    for(int i= mid;i>= low;--i)
    {
        sum += array[i];
        if(sum > left_maxsum)
        {
            left_maxsum=sum;
           
        }
    }

    sum=0;
    for(int i=mid+1;i<=high;++i)
    {
        sum += array[i];
        if(sum > right_maxsum)
        {
            right_maxsum=sum;
            
        }
    }
return(left_maxsum+right_maxsum);
    
//cout<<"maxsum_crossing_mid"<<left_maxsum+right_maxsum<<endl;
}

int max(int a, int b, int c)
{
	if(a>=b && a>=c)
		return a ;
	else if(b>=a && b>=c)
		return b;
	else
		return c;
}
/*
* find a subarray on the left or right side of mid
*/
int find_max_subarray(vector<int> array, int low, int high)
{
	
    
    if(low==high)
    {
       
	return array[low];
    }
    int mid = int((low+high)/2);
    int low_maxsum = find_max_subarray(array, low, mid);
    int high_maxsum = find_max_subarray(array, mid+1, high);
    int crossing_mid_maxsum = find_max_crossing_subarray(array, low, mid, high);
    return max(low_maxsum, high_maxsum, crossing_mid_maxsum);
}
int main()
{
    vector<int> array;
    for(int i=0;i<10;i++)
    {
        int j = 50-rand()%100; //-49~50
        array.push_back(j);
    }

    for(vector<int>::iterator it=array.begin();it!=array.end();++it)
    {
        cout<<*it<<" ";
    }
cout<<endl;
int maxsum =find_max_subarray(array, 0, array.size()-1);
cout<<"the maxsum="<<maxsum<<endl;
//cout<<"range from"<<array[a[1]]<<"to"<<array[a[2]]<<endl;
return 0;
}

3 增量算法（插入算法）

假设已知A[1~N]的最大顺序子序列和，那么对于A[1~N+1]序列，增加一个项，最大顺序子序列和会在哪里产生呢？（1）不变，A[N+1]项不影响（2）在包括A[N+1]项往前的子序列中产生。

#include <iostream>
#include <cstdlib>
#include <vector>

using namespace std;

int enlarge(vector<int> array,int maxsum, int i)
{
	if(i>array.size() || i<=0)
		return -1;
	int sum=0;
	for(int j=i;j>=0;--j)
		sum += array[j];
	if(sum>maxsum)
	maxsum=sum;
	return maxsum;
}
int find_maxsum(vector<int> array)
{
	if(array.empty())
		return -1;
	int maxsum=array.at(0);
	for(int i=1;i<=array.size()-1;++i)
	{
		int result = enlarge(array, maxsum, i);
		if(result>maxsum && result != -1)
			maxsum = result;
	}
	return maxsum;
}
int main()
{
	vector<int> array;
	for(int i=0;i<10;++i)
		array.push_back(10-rand()%20);
	for(vector<int>::iterator it= array.begin();it != array.end();++it)
		cout<<*it<<" ";
	cout<<endl;
	int max = find_maxsum(array);
	cout<<"maxsum ="<<max<<endl;
	return 0;
}

复杂度 O（n^2）

4 最优解（线性复杂度 O(N)）

参考：http://www.cnblogs.com/CCBB/archive/2009/04/25/1443455.html

//线性的算法O(N) 
long maxSubSum4(const vector<int>& a) 
{ 
       long maxSum = 0, thisSum = 0; 
       for (int j = 0; j < a.size(); j++) 
       { 
              thisSum += a[j]; 
              if (thisSum > maxSum) 
                     maxSum = thisSum; 
              else if (thisSum < 0) 
                     thisSum = 0; 
       } 
       return maxSum; 
}