O(nlogn) algorithm for The LIS
We already know about the quadratic time LIS approach using Dynamic Programming.
Today, we gonna see and understand the shortest O(nlogn) approach for LIS.
Let the sequence be A = {3,6,5,4,7,10}
We know the LIS lengths for each index is {1,2,2,2,3,4}
Approach:
We will loop over the array and store the LIS at each index in a separate vector. If the incoming element is smaller than any element in our LIS, then we take the lower bound to find the next greater element and replace it with the current element. This is because replacing the element will not change the LIS length and also if a smaller element is added to LIS, then we can get more advantages from future elements.
For example let our sequence be just S ={ 3, 6, 4, 5}
If we consider the LIS for the first index = {3}
If we consider the LIS for the Second index = {3,6}
But, when we consider the LIS for the third index, we have two options: {3,6} or {3,4}.
We will choose {3,4} because 4 is less than 6. The advantage will be clear on the very next index.
When we consider the LIS for the fourth index = {3,4,5}. But, if we had chosen {3,6} on the third index, we would have missed the 5 because {3,6,5} is not LIS.
So, at every possible index, we just find the lower_bound of the current element and if it exists in the vector of LIS, we replace that with our element. If it does not exist, we simply push our element because it is the largest element in our LIS.
To know the LIS at any particular index, we can simply check out the size of our vector.
vector<int> v;
for (int i = 0; i < n; i++) {
auto it = lower_bound(v.begin(), v.end(), a[i]);
if (it != v.end()) *it = a[i];
else v.push_back(a[i]);
}
return v.size();
This finds a strictly-increasing LIS, but you can easily modify it to find the longest nondecreasing sequences by changing
lower_bound to upper_bound.
No comments:
Post a Comment