（一） 問題描述
給定由n個整數（可能為負整數）組成的序列a1，a2，a3，···，an，求該序列的子段和的最大值。當所有整數均為負整數是定義其最大子段和為0，一次定義，所求的最優質值為：max{0、max子段和}。

（二） 算法描述
動態規劃法的基本思想：
動態規劃算法通常用于求解具有某種最優性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應于一個值，我們希望找到具有最優值的解。
算法設計：
#include "stdafx.h"
int MaxSum(int a[],int n,int &Start,int&End){
intsum=0;
int*b,t;
b=newint[n+1];
b[0]=0;
for(inti=1;i<=n;i++){
if(b[i-1]>0){
b[i]=b[i-1]+a[i];
}
else {
b[i]=a[i];t=i;
}
if(b[i]>sum){
sum=b[i];
Start=t;
End=i;
}
}
delete[]b;
returnsum;
}

int main(int argc, char* argv[])
{
inta[7]={0,-2,11,-4,13,-5,-2},sum,Start,End,i;
sum=MaxSum(a,6,Start,End);
for(i=Start;i<=End;i++){
printf("%d ",a[i]);
}
printf("\n%d\n",sum);
getchar();
getchar();
return0;