求递增子字符串的最大和,注意是最大和,子字符串不一定最长,这个WA了。

比如:4 1000 1 3 4, 最大是1000, 而不是1+3+4, 比如:4 1 4 3 1000 应该是 1 + 4 + 1000 = 1005


题目:飞机票直达(A - Super Jumping! Jumping! Jumping!


代码:

Memory: 1732 KB
Time: 15 MS
Language: C++
Result: Accepted
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1000+10;
int org[maxn], sum[maxn];
int n, i, j, ans, imax;
int main()
{
    while(~scanf("%d", &n) && n)
    {
        for(i=0;i<n;i++)
        {
            scanf("%d", &org[i]);
            sum[i]=org[i];
        }
        ans=sum[0];
        for(i=1;i<n;i++)
        {
            imax=0;
            for(j=0;j<i;j++)
            {
                if(org[i]>org[j] && org[i]+sum[j]>sum[i])
                    sum[i]=org[i]+sum[j];
            }
            if(sum[i]>ans)ans=sum[i];
        }
        printf("%d\n", ans);
    }
    return 0;
}