intro-dp-exmp4.cpp

int A[MAX_N]; // assume data is in A[1..n]
int dp[MAX_N];

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

cout << ans << endl;