HDU 1024题目是一道经典的DP问题，它的基础问题是HDU 1003。问题描述大致为：给定输入n，m和数组，然后把长度为n的数组划分成互不交叉的m个子段，要求输出m个子段和的最大值。

　　DP问题的关键是分析题目要求，写出递归公式。数组为a[](本文中数组下标从1开始计数)，把长度为i的数组划分成j段，各段的和用函数f(i,j)表示，且a[i]包含在j段中的某一段。要求出f(i,j)，就是把a[i]加入到划分的段中，分为以下两种情况：

　　1)a[]中前i-1个元素已经划分成j段，只需把a[i]放入第j段中，此时f(i,j)=f(i-1,j)+a[i];

　　2)a[]中前i-1个元素划分为j-1段，则a[i]单独作为第j段。此时f(i,j)=max{f(k,j-1)}+a[i],其中 j-1<=k<=i-1。

　　综合1)和2)，f(i,j)=max{f(i-1,j)+a[i],max{f(k,j-1)}+a[i]}=max{f(i-1,j),f(k,j-1)}+a[i],其中j-1<=k<=i-1 （*）。

　　递推公式有了，考虑初始情况，f(i,1)就是a[]前i个元素中各个子串和的最大值，即HDU 1003。显然，f[i,i]=∑a[i]=g(i)。

     可以把f(i,j)看做是二维数组，最终f(i,m)列中的最大值就是所求的结果。

　  但是仔细分析计算过程可以发现，f(i,j)只与f(i-1,j)和f(k,j-1)列中最大元素有关，我们可以记录下f(i,j)中每列的最大值，记为h(j)，f(i,j)可以简化成如下公式：

　　　　f(i)=f(i-1)+h(i-1) i>=2 ;h(i)=h(i)>f(i)?h(i):f(i)  (**)。

　　注意简化公式过程，在二维数组情况下是从左向右计算，而在一维数组情况下变成从右向左，因为f(i)需要用到没有更新前的f(i-1);

　　实现程序如下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define N 1000000#define M 1000000int f[N],a[N],g[N],h[N];//int *g,*h;void init(int n){
   //计算f(i,1)    int i;    //g=(int *)malloc(sizeof(int)*(n+1));    g[1]=a[1];        for(i=2;i<=n;i++){        if(g[i-1]+a[i]>a[i]){            g[i]=g[i-1]+a[i];        }        else{            g[i]=a[i];        }    }    //printf("%d ",g[1]);    for(i=2;i<=n;i++){        if(g[i]
         
          m)            t=m+1;                for(j=t-1;j>=2;j--){
   //从右向左算            if(h[j-1]>f[j]){                f[j]=h[j-1];            }            f[j]+=a[i];            if(h[j]