lcs

又开始水题了，lcs变形，状态转移条件稍微更改一下即可，lcs是求上升子序列的长度，因此

这里是求最大和，因此

ps：这题明明和上一题基本一样

int main() {
    ll n, a[MAX], dp[MAX];
    while (cin >> n) {
        for (int i = 0; i < n; i++)cin >> a[i], dp[i] = a[i];
        for (int i = 1; i < n; i++)
            for (int j = 0; j < i; j++)
                if (a[i] > a[j] && dp[j] + a[i] > dp[i])
                    dp[i] = dp[j] + a[i];
        ll res = 0;
        for (int i = 0; i < n; i++)res = max(res, dp[i]);
        cout << res << endl;
    }
}