hdu1087 dp

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<string>
 5 #include<cstdio>
 6 
 7 using namespace std;
 8 
 9 int n;
10 int a[1010];
11 
12 int main(){
13     
14     while(cin >> n){
15         if(!n)    break;
16         
17         for(int i = 1 ; i <= n ; i++){
18             cin >> a[i];
19         }
20         
21         int dp[1010];
22         int res = 0;
23         memset(dp, 0, sizeof(dp));
24         dp[1] = a[1];
25         
26         for(int i = 2 ; i <= n ; i++){            
27             for(int j = i - 1 ; j >= 1 ; j--){
28                 if(a[i] > a[j]){
29                     dp[i] = max(dp[i], dp[j] + a[i]);
30                 }else{
31                     dp[i] = max(dp[i], a[i]);
32                 }            
33                 res = max(res, dp[i]);
34             }
35         }
36         
37         cout << res << endl;        
38     }
39         
40     return 0;
41 }