动态规划之数列的最大和

Super Jumping! Jumping! Jumping!
该题作为动态规划的讲解例子，首先需要明白动态规划问题和非动态规划问题的本质题意区别，即题意的明白和解决。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
    int m,n,a[1010],dp[1010],i,j;//初始化开始，用数组a来存放原先的键入数据。
    while(scanf("%d",&m),m)
    {
        for(i=0;i<m;i++)
        scanf("%d",&a[i]);//数据存入
        int max=0; 
        for(i=0;i<m;i++)
        {
            dp[i]=a[i];//先将数据都放入dp数据
            if(dp[i]>max)
            max=dp[i];//max表示当前所有的已输入的数据的最大和
            for(j=0;j<i;j++)
            {
                if(a[j]<a[i]&&dp[j]+a[i]>dp[i])
                dp[i]=dp[j]+a[i];//（找到当前max的方法）逐个将此前的所有dp数组的值与加上当前数的和作比较，得到dp[i]
            }
            if(dp[i]>max)
            max=dp[i];//将dp[i]赋予max使max值更新。
        }
        printf("%d\n",max);//输出max
    }
    return 0;
 }```
首先，根据题意得，该题要求的是最大和。（在一组数据里提取子序列，每一组的前一个数都小于后一个数）。在我们之前做过的一道加工木材的题相似，例如：一个序列是：1 2 9 2 3 4 5 6 7 8
那么一种可能是先1，再2，然后9，没有比9更大的，故得分为9+2+1=12。另一种可能为取序列1 2 3 4 5 6 7 8，最大为8，那么所得分明显是比前一个大的。这种问题的解决需要用到的明显就是动态规划。
可是首先，我们并不知道以哪一个数字为最大的比较好，所以增加了辅助数组来作为标记。