The Longest Increasing Subsequence

                            Solution in C :

In C++ :





#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <ctime>

using namespace std;

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define forit(s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it ++)
#define N 1000100
#define all(a) a.begin(), a.end()
#define ll long long
#define pii pair <int, int>
#define sz(a) (int)a.size()
#define vi vector <int>
#define forn(i, n) for(int i = 0; i < n; i ++)

const int inf = (int)(1e9);
const int mod = inf + 7;
const double pi = acos(-1.0);
const double eps = 1e-9;

int n, a[N];

int main () {

    #ifdef LOCAL
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    #endif

    cin >> n;
    for(int i = 0; i < n; i++) scanf("%d", a + i);
    vector <int> d(N, 0);

    d[0] = -inf;
    for(int i = 1; i < N; i++) d[i] = inf;

    for(int i = 0; i < n; i++) {
        int j = upper_bound(all(d), a[i]) - d.begin();
        if(d[j - 1] < a[i] && a[i] < d[j]) d[j] = a[i];
    }

    for(int i = N - 1;; i--) {
        if(d[i] != inf) {
            cout << i;
            return 0;
        }
    }

    return 0;
}








In Java :





import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner reader = new Scanner(System.in);
        int n = reader.nextInt();
        int[] array = new int[n];
        for(int i = 0 ; i < n; i++ )
        {
            array[i] = reader.nextInt();
        }
        System.out.println(getLengthOfLIS(array));
    }
    public static int getLengthOfLIS(int[] array)
    {
        TreeSet<Integer> s = new TreeSet<Integer>();
        for( int i = 0 ; i < array.length ; i++)
        {
           //if array[i] is newly added?
           if( s.add(array[i]) )
           {
               //if array[i] is not the last element?
               if( array[i] != s.last() )
               {
                    //remove it's next element; s.higher() gives the least element 
                   //which is greater than array[i]
                   s.remove(s.higher(array[i]));
               }
           }
        }
        return s.size();
    }
}








In C :





#include <stdio.h>

int n,a[1000000],b[1000000]; 

int getRight(int *Arr,int left,int right,int value)
{
    int mid;
    while(right>left+1)
    {
        mid=left+(right-left)/2;
        if(Arr[mid]>=value)right=mid;
        else left=mid;
    }
    return right;
}
 
int CalcLIS()
{
    int i,res=1;
    b[0]=a[0];
    for(i=1;i<n;i++)
    {
        if(a[i]<b[0])
            b[0]=a[i];
        else if(a[i]>b[res-1])
            b[res++]=a[i];
        else
            b[getRight(b,-1,res-1,a[i])]=a[i];
    }
    return res;
}
 
int main()
{
    int i;
    scanf("%d",&n);
    for(i=0;i<n;i++)scanf("%d",&a[i]);
    printf("%d",CalcLIS());
    return 0;
}








In Python3 :





import bisect

N = int(input())
A = [int(input()) for c in range(N)]
P = [0] * N
M = [0] * (N + 1)
L = 0

for i in range(N):
    lo, hi = 1, L
    while lo <= hi:
        mid = lo + (hi-lo) // 2
        if A[M[mid]] < A[i]:
            lo = mid+1
        else:
            hi = mid-1
    
    newL = lo
    P[i] = M[newL-1]
    M[newL] = i
    if newL > L:
        L = newL

print(L)