HDU-1087 Super Jumping! Jumping! Jumping!（上升子序列最大和）

和求最长上升子序列的元素个数有点相似，状态转移方程为dp[i]=max(dp[j]+a[i],dp[i])其中a[j]<a[i], 注意要把所有元素都小于0的情况单独拿出来讨论

#include<iostream>#include<cstring>#include<algorithm>using namespace std;const int p=-0x3f3f3f3f;int main(){	int n;	long long a[1000+1];	long long dp[1000+1];	int flag;	while(cin>>n&&n!=0){		flag=0;		memset(dp,p,sizeof(dp));		dp[0]=0;		for(int i=1;i<=n;i++){			cin>>a[i];			if(a[i]>=0) flag=1;		}		for(int i=1;i<=n;i++){			for(int j=0;j<i;j++){				if(a[j]<a[i]) dp[i]=max(dp[j]+a[i],dp[i]);//因为j从0开始递增且dp[0]=0,就使得dp[i]刚开始就等于a[i]			}		}		if(!flag){			sort(a,a+n+1);			cout<<a[n-1]<<endl;			continue;		}		sort(dp,dp+n+1);		cout<<dp[n]<<endl;	}	return 0;}