We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. The Longest Increasing Subsequence
  5. Discussions

The Longest Increasing Subsequence

  • thinhproee
     + 1 comment
    //O(nlogn)
// 
#include <string>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <cmath>
#include <fstream>
#include <queue>
using namespace std;
using ll=long long;

//F[i] save the last element min it can obtain of increasing subsequence its length = i 
//dung bs
//lowerbound phan tu dau tien >=a[i]
//in: 9
//1 4 2 3 8 10 6 9 13
//out:6
//ket qua:1 2 3 6 9 13








int main()
{ 
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int n;cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];

    vector<int> res;
    res.push_back(a[0]);
    for(int i=1;i<n;i++)
    {
        auto it =lower_bound(res.begin(),res.end(),a[i]);
        if(it==res.end())
            res.push_back(a[i]);
        else
            *it=a[i];
        // for(int x:res)
        //     cout<<x<<' ';
        // cout<<endl;
    }
    //cout<<endl;
    cout<<res.size();
}