问题描述：给定N个整数（可能是负整数）组成的序列，求该序列的最大子段和。

该问题的动态规划方程为：b[j]={b[j-1]+a[j],a[j]}

代码：

#include "stdafx.h"#include
     
      using namespace std;#define N	6int _tmain(int argc, _TCHAR* argv[]){	cout<<"----------最大子段和---------"<
      
       0)			b+=data[i];	//b[j]=max{b[j-1]+a[j],a[j]}		else		{			b=data[i];		}		if(b>sum)sum=b;	}		return sum;}//MaxSum
      
     

该问题动态规划算法的时间复杂度为O(n)，简单。