1 #include<stdio.h>
2 #include<algorithm>
3 using namespace std;
4 const int maxn = 1005;
5 int a[ maxn ],dp[ maxn ];//dp[i]表示以a[i]结尾的子序列的和最大
6 int main(){
7 int n;
8 while( scanf("%d",&n)!=EOF && n ){
9 for( int i=0;i<n;i++ )
10 scanf("%d",&a[ i ]);
11 int ans=a[ 0 ];
12 dp[ 0 ]=a[ 0 ];
13 int sum;
14 for( int i=1;i<n;i++ ){
15 sum=0;
16 for( int j=0;j<i;j++ ){
17 if( a[ j ]<a[ i ] && sum<dp[ j ] )
18 sum=dp[ j ];
19 }
20 dp[ i ]=sum+a[ i ];
21 ans=max( ans,dp[ i ] );
22 }
23 printf("%d\n",ans);
24 }
25 return 0;
26 }
View Code
