dp[i]=max{dp[i],dp[j]+dp[i]} a[i]>a[j]
初始化dp[i]=a[i];
//最大上升子段和 #include<iostream> #include<cstdio> #include<cstring> #define maxn 10000 #define INF 0x7fffffff using namespace std; int a[maxn],dp[maxn]; int max(int x,int y) { return x>y?x:y; } int main() { int n; while(scanf("%d",&n)!=EOF) { if(n==0) break; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); dp[i]=a[i]; } for(int i=1;i<=n;i++) { for(int j=i-1;j>=1;j--) { if(a[i]>a[j]) { dp[i]=max(dp[i],dp[j]+a[i]); } } } int Max=-INF; for(int i=1;i<=n;i++) { if(Max<dp[i]) Max=dp[i]; } printf("%d\n",Max); } return 0; }