最大上升子序列和

/*
状态转移方程
sum[i] = max{1, sum[j] + 1} i < j and A[i] > A[j]
边界
sum[i] = A[i] (i = 1, 2, ... n)
*/
#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;
const int N = 1000;

int A[N], sum[N];
int main()
{
    int n;
    while (~scanf("%d", &n))
    {
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &A[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            sum[i] = A[i];
            for(int j = 0; j <= i; j++){
                if(A[j] < A[i]){
                    sum[i] = max(sum[i], sum[j] + A[i]);
                }
            }
            ans = max(ans, sum[i]); 
        }

        printf("%d\n", ans);
    }
    return 0;
}