和求最長(zhǎng)上升子序列的元素個(gè)數(shù)有點(diǎn)相似，狀態(tài)轉(zhuǎn)移方程為dp[i]=max(dp[j]+a[i],dp[i])其中a[j]<a[i], 注意要把所有元素都小于0的情況單獨(dú)拿出來討論

#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]);//因?yàn)閖從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;}