[数据结构与算法]HDOJ 1087

题目意思即为递增的子序列 使其和最大
(动态规划）
我们不妨设dp[i]表示以第i个数结尾的递增子序列的最大和
则不妨设dp[0] = 0;
对于第i个数结尾这个过程
我们考虑dp[i]从哪里来，为满足题设条件，必须从头遍历找到a[x] < a[i]对所有满足条件的a[x];dp[x]表示以第x个数结尾的子序列最大和,有动态规划原理，要满足最优子结构，既说明需枚举所有的x，找出其中dp[x]+a[i]的最大值 ，a[i]表示第i 个数的权值;
然后进行打表一直枚举到dp[n]即可；
ac代码如下`

#include <iostream>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int a[1000]={0};
int dp[1000];
int main(){
    int n;
    int i;
    int ans;
    while(cin>>n && n!= 0){
        for(int i=0;i<n;i++){
            cin>>a[i];
            dp[i] = a[i];
        }
        ans = 0;
        for(int i=0;i<n;i++){
            
            for(int j=0;j<=i;j++){
                if(a[j] < a[i]){
                    dp[i]  = max(dp[j]+a[i],dp[i]);
                }
            }
            ans = max(ans,dp[i]);
        }
        cout<<ans<<endl;
        
    }
    //cout<<ans<<endl;

   
    
    return 0;
}