数组最大子序列和

// 数组的最大子序列和：
// 连续的子数组，和为最大。
//设sum[i] 为前i个元素中，包含第i个元素且和最大的连续子数组，
//result 为已找到的子数组中和最大的。
//对第i+1个元素有两种选择：做为新子数组的第一个元素、放入前面找到的子数组。
//sum[i+1] = max(a[i+1], sum[i] + a[i+1])
//result = max(result, sum[i])

#include <iostream>   
using namespace std;
#include <iterator>
int maxsum(int ap[], int n, int &a, int &b)      
{  
	int max=ap[0];        
	int sum=ap[0]; 
	int p1=0, p2=0;
	for(int j=1;j<n;j++)  
	{  
		if(sum<0)      
		{
			sum=ap[j];  
			p1=p2=j;
		}
		else     
		{
			sum+=ap[j];    
			p2=j;
		}
		if(sum>max)  
		{
			max=sum;  
			a=p1;
			b=p2;
		}
	}  
	return max;  
}  

int main()  
{  
	int ap[]={-1, -2, 3, 10, -4, 7, 2, -5};  
	int ap2[]={-91, -2, -3, -10, -4, -7, -2, -5};  

	int a,b;
	copy(ap,ap+8,ostream_iterator<int>(cout," "));
	cout<<endl<<"maxsum:"<<maxsum(ap, 8,a,b)<<endl;  
	copy(ap+a,ap+b+1,ostream_iterator<int>(cout," "));
	cout<<endl<<endl;

	copy(ap2,ap2+8,ostream_iterator<int>(cout," "));
	cout<<endl<<"maxsum:"<<maxsum(ap2, 8,a,b)<<endl;  
	copy(ap2+a,ap2+b+1,ostream_iterator<int>(cout," "));
	cout<<endl<<endl;

	return 0;  
}

 

 

思路：记录sum的值，sum依次统计序列元素的和，如果sum<0，则丢弃之前的sum值，采用新的值sum=p[i]。

DP递推时，需要比较sum与最大值max，取其较大者。