MAK's LIS Implementation

LIS_nlgn.cpp

/*
 * Copied from: https://paste.ofcode.org/e2wNKmt5QyriNTeEZYbNei
 * In case that paste content expires
 */
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf=100000000;

int findPositionUsingBinarySearch(vector<int> &aseq,int key,int low,int hi){
    if (low>hi)
        return low;// this is the crossover. It means  key<aseq[low] but key>=aseq[hi] and hi+1=low
    int mid=low+(hi-low)/2;
    if (key<=aseq[mid])
        return findPositionUsingBinarySearch(aseq,key,low,mid-1);
    return findPositionUsingBinarySearch(aseq,key,mid+1,hi);
    
    
}
int LIS(vector<int> &A){
    int n=A.size();
    //filling an array with inf. It is gonna hold a sequence of number in increasing order
    vector<int> aseq(n+1,inf);
    
    aseq[0]=-inf; // aseq=[-inf,inf,inf....inf];
    int LastIndexOfTheCurrentSequence=0;
    for(int i=0;i<n;i++){
        
        int pos=findPositionUsingBinarySearch(aseq,A[i],0,LastIndexOfTheCurrentSequence);
        aseq[pos]=A[i];
        LastIndexOfTheCurrentSequence=max(LastIndexOfTheCurrentSequence,pos);
        //LastIndexOfTheCurrentSequence will be updated if aseq[pos]=A[i] replaces inf in aseq;
        
    }
    
    return LastIndexOfTheCurrentSequence;
     
}
int main() {
    int N;

    cin>>N;
    vector<int> A(N);
    for(int i=0;i<N;i++)
        cin>>A[i];
    cout<<LIS(A)<<endl;
    
    return 0;
}