CSES : Increasing Subsequence - dynamic Programming

 Problem Statement:

You are given an array containing n$n$ integers. Your task is to determine the longest increasing subsequence in the array, i.e., the longest subsequence where every element is larger than the previous one.

A subsequence is a sequence that can be derived from the array by deleting some elements without changing the order of the remaining elements.

Input

The first line contains an integer n$n$: the size of the array.

After this there are n$n$ integers x1,x2,…,xn$x_1,x_2,\dots ,x_n$: the contents of the array.

Output

Print the length of the longest increasing subsequence.

Constraints

• 1≤n≤2⋅105$1\le n\le 2\cdot {10}^5$
  
• 1≤xi≤109$1\le x_i\le {10}^9$
  

Example

Input:
8
7 3 5 3 6 2 9 8

Output:
4




Full Video Explanation:

Youtube Video Explanation




Code:(C++)

#include <bits/stdc++.h>
using namespace std;

int main() {

  int n;
  cin >> n;
  vector<int> dp;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    auto it = lower_bound(dp.begin(), dp.end(), x);
    if (it == dp.end()) {
      dp.push_back(x);
    } else {
      *it = x;
    }
  }
  cout << dp.size() << endl;
}