每日一題之 hdu 1087

題意：

給你n個數，找到一個子序列單調遞增，且其所有元素的和最大。

Sample Input

3 1 3 2

4 1 2 3 4

4 3 3 2 1

Sample Output

4

10

3

思路：

依照最長上升子序列的思想，用 dp[i] 表示以 A[i]結尾的子序列中，和最大的值。注意這裡并不是求最長上升子序列。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn = +;

int A[maxn];
long long dp[maxn];

int main()
{
    int n;
    while() {
        cin >> n;
        if (n == ) break;
        long long res = ;
        memset(A,,sizeof(A));
        memset(dp,,sizeof(dp));
        for (int i = ; i < n; ++i)
            cin >> A[i];


        dp[] = A[];
        for (int i = ; i < n; ++i) {
            dp[i] = A[i];
            for (int j = ; j < i; ++j) {
                if (A[j] < A[i]) {
                    dp[i] = max(dp[i],dp[j]+A[i]);

                }
            }
            res = max(dp[i],res);
        }

        cout << res << endl;

    }
    return ;
}