Longest_increasing_subsequence.cpp

/* DP Execrise */
#include <iostream>

using namespace std;

const int MAX_LEN = 1000;
int seq[MAX_LEN];
int lis[MAX_LEN];

int main()
{

    int n;
    cin >> n;

    for (int i =0; i < n; ++i) {
        cin >> seq[i];
        lis[i] = 1;
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (seq[i] > seq[j]) {
                lis[i] = max(lis[i], lis[j] + 1);
            }
        }
    }

    int max = 0;
    for (int i : lis)
        if (i > max)
            max = i;

    cout << max << endl;

    return 0;
}