Super Jumping! Jumping! Jumping! HDU-1087最長上昇サブシーケンス(基礎dp特集)

長さnのシーケンスが与えられ、その中に必ず1つの要素と最大の厳密な上昇サブシーケンスが存在し、このシーケンスの要素和を求める.Inputは複数組の入力データを含み、各組のデータは1行を占め、各行は整数n、次いでn個の数a_1, a_2, …, a_n(a_iは32ビット符号整数範囲)、n=0は入力終了(0<=n<=1000)を示す.Outputの数は、サブシーケンスの最大要素と厳密に上昇します.Sample Input 3 1 3 3 2 4 1 3 4 4 3 3 3 3 2 1 15 1 88 49 78 57 48 7 3 4 4 4 8 9 7 2 0 Sample Output 4 10 3 136バックプレートif(a[j]

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define maxn 1005
int main()
{
     
	int n;
	int a[maxn];
	int dp[maxn];
	while(~scanf("%d",&n)!=EOF){
     
		if(n==0) break;
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++){
     
			cin>>a[i];
			dp[i]=a[i];
		}
		for(int i=2;i<=n;i++){
     
			for(int j=1;j<i;j++){
     
				if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+a[i]);
			}
		}
		int ans=0;
		for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
		cout<<ans<<endl;
	}
  return 0;
}