Longest Increasing Subsequence - Binary Search

#include <bits/stdc++.h>
using namespace std;
#define int long long
int LIS(int a[],int n)
{
    int parent[n+1];
    int sub[n+1];
    memset(sub,1e9,sizeof sub);
    int length=0;
    for(int i=0;i<n;i++)
    {
        int low=1;
        int high=length;
        while(low<=high)
        {
            int mid=(low+high)/2;
            if(a[sub[mid]]< a[i])
                low=mid+1;
            else
                high=mid-1;
        }
        int pos=low;
        parent[i]=sub[pos-1];
        sub[pos]=i;
        length=max(length,pos);
    }
    return length;
}
signed main()
{

    int n;
    cin >> n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin >> a[i];
    }

    cout<<LIS(a,n)<<'\n';



    return 0;
}