给定由n个整数（可能为负数）组成的序列 a1 , a2 , ... , an
求该序列形如 for k = i to j : sum = sum + ak : next k
的子段和的最大值.
问题有很多解法，而用动态规则解是最简单的。
设
b[j] = max(1<=i<=j) { sum( i , j ) } , 1 <= j <= n
则
b[j] = max{ b[j-1] + a[j] , a[j] } , 1 <= j <= n
动态规则问题最重要的是得出
递归式
而这正是问题的难点，至少对我来说比较难
分析问题，找到问题是否有最优子结构，由最优子结构的性质得出
递归式
////////////////////////////////////////////////////////////
#include "iostream.h"
int MaxSum( int n , int *a , int &besti , int &bestj )
{
int sum = 0;
int begin = 0;
int t = 0;
besti = -1;
bestj = -1;
for( int i = 0 ; i < n ; i++ )
{
if( t > 0 )
{
t += a[i];
}
else
{
t = a[i];
begin = i;
}
if( t > sum )
{
sum = t;
besti = begin;
bestj = i;
}
}
return sum;
}
void main()
{
int a[] = { -2 , 11 , -4 , 13 , -5 , -2 };
int n = 6;
int bi , bj;
int best = MaxSum( n , a , bi , bj );
cout<<"最大子段和为:"<<best<<endl;
cout<<"起点 "<<bi<<" 终点 "<<bj<<endl;
}
////////////////////////////////////////////////////////////
参考资料：
《计算机算法分析与设计》电子工业出版社
程序有所改进