题意：其实就是最大递增子段和
思路：状态方程:dp[j]=max{dp[i]}+a[j]; 其中,0<=i<=j,a[i]<a[j]
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstdlib> 5 #include<cstdio> 6 #include<set> 7 #include<map> 8 #include<vector> 9 #include<cstring> 10 #include<stack> 11 #include<cmath> 12 #include<queue> 13 #include <bits/stdc++.h> 14 using namespace std; 15 #define INF 0x3f3f3f3f 16 #define ll long long 17 #define clc(a,b) memset(a,b,sizeof(a)) 18 19 int main() 20 { 21 int a[1005]; 22 int dp[1005]; 23 int n; 24 while(~scanf("%d",&n),n) 25 { 26 for(int i=0;i<n;i++) 27 { 28 scanf("%d",&a[i]); 29 dp[i]=a[i]; 30 } 31 int maxx=a[0]; 32 for(int i=0;i<n-1;i++) 33 { 34 for(int j=i+1;j<n;j++) 35 { 36 if(a[j]>a[i]) 37 dp[j]=max(dp[j],dp[i]+a[j]),maxx=max(maxx,dp[j]); 38 } 39 } 40 cout<<maxx<<endl; 41 } 42 return 0; 43 }