hdoj

hdu-1087.cpp

/*
	hdu-1087
	Super Jumping! Jumping! Jumping!
	http://acm.hdu.edu.cn/showproblem.php?pid=1087
*/
#include <iostream>
#include <cstdio>

using namespace std;

int n;
int item[1001];
int dp[1001];
int result;
int main(){
#ifndef ONLINE_JUDGE
	freopen("in", "r", stdin);
	//freopen("out", "w", stdout);
#endif
	while(cin>>n,n){
		for(int i=0;i<n;i++){
			cin>>item[i];
		}
		result=dp[0]=item[0];
		for(int i=1;i<n;i++){
			dp[i]=item[i];
			for(int j=0;j<i;j++){
				if(item[i]>item[j]){
					if(dp[j]+item[i]>dp[i])
						dp[i]=dp[j]+item[i];
				}
			}
			result=result>dp[i]?result:dp[i];
		}
		cout<<result<<endl;
	}
	return 0;
}