http://acm.hdu.edu.cn/showproblem.php?pid=1087
题意:求最大递增子段和。
思路:与求最长上升子序列异曲同工。
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int INF = 0x3f3f3f3f; int main() { int n,a[1010]; int dp[1010]; while(~scanf("%d",&n) && n) { for(int i = 1; i <= n; i++) scanf("%d",&a[i]); memset(dp,0,sizeof(dp)); int ans = -INF; for(int i = 1; i <= n; i++) { dp[i] = a[i]; for(int j = 1; j < i; j++) { if(a[j] < a[i] && dp[i] < dp[j]+a[i]) dp[i] = dp[j]+a[i]; } ans = max(ans,dp[i]); } printf("%d\n",ans); } return 0; }