Longest increasing subsequence(LIS) in O(nlogn) 🚩🚩🚩

// This is a  (dynamic programing + binary search) approach which takes O(nlogn) time
/*
Steps:-

-->main LIS function
 1.create a ans array and push first element of given array in it.
 2.now,from second element of given array traverese till end and to the following
         if->  current element is bigger than the element at back of ans array
                     push it in the ans array

         else ->
             find the index where the curr element can fit in ans array using binary search pass the ans array,size of ans array and curr element as a parameters to binary search function.

 3.size of ans array is the length of LIS


-->binary search function
 1.just do the general binary search ,but if the target element is not found instead of returning -1 return the low.

note:- here,low indecates the position where the target should be placed in ans array.

*/

int give_index_using_binary_search(vector<int> ar, int n, int tar)
{
    int low = 0, high = n - 1;

    while (low <= high)
    {
        int mid = low + (high - low) / 2;
        if (ar[mid] == tar)
            return mid;
        else if (ar[mid] > tar)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return low;
}

int LIS(vector<int> &ar, int n)
{

    vector<int> ans;
    ans.push_back(ar[0]);

    for (int i = 1; i < n; i++)
    {
        if (ans.back() < ar[i])
            ans.push_back(ar[i]);
        else
        {
            int ind = give_index_using_binary_search(ans, ans.size(), ar[i]);
            ans[ind] = ar[i];
        }
    }

    return ans.size();
}