問題描述:
給定一個長度為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> }