Longest increasing Subsequence in nlogn time

/*Thus We are on a great topic Longest Increasing Subsequence in nlog(n) time if n is the length of given array .

Cool Now let us discuss O(n^2) dp method first OK

algo is plain
ll ans[n+1]={0};
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
if(a[j]<a[i])
{
ans[i]=max(a[i]+ans[j])
}
}
}
This is plain O(n^2) algo as you know well as it is travering all the case just a modified brute force
which we commonly call dp.

Now same problem can be solved in O(nlogn) time using a greedy strategy not dynamic strategy.

Just think we are on an element i thus what we want is that maximum element whose index in the pretraversed array that
<i and whose value is less than a[i].Just think of it how can you obtain in log(n) time it can be done with many known algos like binary search lower bound upperbound segment trees and ya set or map in c++

Now think of why I told previous statement to think of that

Let me describe a state i as at this position we will store the length of LONGEST INCREASING SUBSEQUENCE WHOSE LAST ELEMENT IS A[i]

If you can think of it that what I meant then coming statements will be easy for you to think of.

consider a set and a map
in set at present we will store the value at first index and Longest increasing subsequence ending at a[1] currently is 1

se.insert(a[1])//set
mp[a[1]]=1;//map

So now coool
and traverse whole array
and for each index i find out the maximum element present in the current set
which is less than a[i]
let us keep value of this element as val;

and update the LIS for mp[a[i]]=mp[val]+1//map look at this statement carefullly as it does many things.
and insert the current element a[i] inside the set
after full traversal from 2 to n we can find maximum LIS by keeping account of max(ans,mp[a[i]])
for all i from 1 to n; Cool

Proof:-

Now Question Arises that why we chose such (maximum val_)< a[i] for every a[i] from the set and updated in the map.
becuse if there exists another value <val then that value must be sure considered under val because initially the set was empty and when we
update mp[val] then we have already considered some value in the set which is less than value.
Hope this makes it clear1

If it is still unclear have a look at following example.

consider case as
5
2 1 4 3 5

for i=1;
so we updated first value in set
set contains value {2} and mp[2]=1(since LIS ending at 2 is 1)

for i=2;
we searched for maximum element less than a[2]=1 in set we got answer as Nill means there is no element less than 1 inside the set so mp[1] =1;
now set becomes {1,2}

for i=3 ;
we search for same thing for a[3]=4 we got value as 2 thus mp[4]=mp[2]+1; ===> mp[4]=2//hopes things are becoming clear yet.
now set becomes{1,2,4}

for i=4
we search for same thing for a[4]=3 we got value as 2(max value less than 3) thus mp[3]=mp[2]+1; ===> mp[3]=2//hopes things are becoming clear yet.
now set becomes{1,2,3,4}

for i=5
we search for same thing for a[5]=5 we got value as 4(max value less than 5) thus mp[5]=mp[4]+1; ===> mp[5]=2+1=3//hopes things are becoming clear yet.
now set becomes{1,2,3,4,5}

loop[ ends ] maximum value present in map is 3 thus LIS is 3.
*/

1 Like

Very Good explanation without using big technical logic