Longest increasing subsequence(LIS) in O(nlogn) 🚩🚩🚩
Mon Jan 24 2022 14:30:12 GMT+0000 (Coordinated Universal Time)
Saved by
@vaibhav_55
// 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();
}
content_copyCOPY
Comments