Challenge: Longest Increasing Subsequence

Lab C++ Advanced 30 points

Print the length of the longest strictly increasing subsequence of n numbers (not necessarily neighbours). For 10 9 2 5 3 7 101 18 it's 4.

Input

Line 1: n (n ≤ 2000). Line 2: n whole numbers.

Output

One number.

Example

Input

8
10 9 2 5 3 7 101 18

Output

Sample input available Sample output available

Editor

C++

Hints

best[i] = longest increasing subsequence ending at i.

best[i] = 1 + max(best[j]) over j < i with a[j] < a[i].

Solution explanation

O(n²). With lower_bound it can be done in O(n log n) – try it later!

Show solution

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n), best(n, 1);
    for (int& x : a) cin >> x;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++)
            if (a[j] < a[i]) best[i] = max(best[i], best[j] + 1);
    cout << *max_element(best.begin(), best.end()) << endl;
    return 0;
}

Output

Answer