問題描述：
給定一個長度為n的整數的數組，現在讓你將整個數組分成m段，並且這m段互不相交，在所有分段方式中能夠得到的這m段子數組的最大的和是多少？
解析：
本題是一道適合用動態規劃方式解決的問題，首先定義兩個狀態：f[i][j]，g[i][j].
f[i][j]是將前i個元素分成j段並且包含第i元素的最大和；
g[i][j]是將前i個元素分成j段並且不一定包含第i元素的最大和；
則狀態轉移方程為：
f[i][j]=max(f[i-1][j]+data[i],g[i-1][j-1]+data[i]),即第i元素data[i]可能和前面的元素一起組成第j段，也可能是自己單獨是第j段；
g[i][j]=max(f[i][j],g[i-1][j]),即g[i][j]為包含第i元素的j段和與不包含第i元素j段和的最大值；
g[n][m]即為最終整個數組分成m段，並且這m段互不相交，在所有分段方式中能夠得到的這m段子數組的最大的和；
下面程序中可以將兩個二維數組f,g壓縮為一維進行計算，程序如下：
<SPAN style="FONT-FAMILY: Times New Roman">#include<iostream>
using namespace std;
int max_sum(const int *data,int n,int m);
int max(int a,int b);
int main()
{
int n,m,i;
cin>>n>>m;
int *data=new int[n+1];
for(i=1;i<=n;i++)
cin>>data[i];
int maxsum=max_sum(data,n,m);
cout<<maxsum<<endl;
delete []data;
return 0;
}
int max_sum(const int *data,int n,int m)
{
int i,j;
int *f=new int[m+1];
int *g=new int[m+1];
for(i=0;i<=m;i++)
{
f[i]=0;
g[i]=0;
}
for(i=1;i<=n;i++)
{
for(j=m;j>=1;j--)
{
f[j]=max(f[j]+data[i],g[j-1]+data[i]);
g[j]=max(f[j],g[j]);
}
}
int result=g[m];
delete []f;
delete []g;
return result;
}
int max(int a,int b)
{
if(a>b)
return a;
else
return b;</SPAN>
}
