Longest Increasing Subsequence

'''
Little tricky problem:
so you can't use the monotonic stack because for eg [1,2,3,-1,4] here once -1 comes, you will pop all and at one point of time, max elments can be in the stack is 3 ie. [1,2,3]

input=[1,7,8,4,5,6,-1,9]
so as monotonic stack won't work in our case so we will have to explore all the subsequence but it will take 2^n time as either you select the element or not select the element.

Instead of thinking about the whole array at once, we focus on one position at a time. so can we do something, where we will go to each element one by one and have the information somehow that what will be the longest increasing subsequence ending to this ie. ith element, But we don't need to know what exactly are the numbers in the subsequence ending at ith element.

input=[1,7,8,4,5,6,-1,9]
Lets maintain an array ie.dp and at the ith position, the length of the dp at that ith position will tell the length of the longest subsequence ending at the ith element position.

at i=0, element=1, dp=[1] -> because obviously if the array is one size ie [1], longest will be 1 size only

at i=1, element=7, dp=[1,7] -> this is also obvious, but focus on the length of the dp is same as LIS of the array ending now or not? don't focus on the elements

at i=2, element=8, dp=[1,7,8] -> this is also obvious, length of LIS of arr=[1,7,8] will be 3

at i=3, element=4, here obvious we can't push 4 at end, for now just think we are replacing 4 with 7 so now arr=[1,4,8] and why with 7 only?-> because if I am forces to push the 4 in the table, I will push in the place of element 7. saying again, this is not the valid subsequence but for the arr=[1,7,8,4] -> it's valid Longest Increasing Subsequence would be [1,7,8] and it's length is also 3 only and our dp has also length 3 after replacemenet so dp=[1,4,8]

at i=4, element=5, we will do same, can't push 5 at end so I will push 5 at the place of 8 so now dp=[1,4,5], so current arr=[1,7,8,4,5] and it's LIS=[1,7,8] or LIS=[1,4,5], which has lenght of 3 and our dp array has also length of 3 only so dp=[1,4,5]

at i=5, element=6, we can place 6 at the end because if we are forced to push 6 in the array and to maintain the increasing order, we will pust at end. so dp=[1,4,5,6] so now current array=[1,7,8,4,5,6] so LIS can be [1,4,5,6] whose size=4 and our current dp as also size 4 so make sense. dp=[1,4,5,6]

at i=6, element=-1, we can replace -1 with 1, because to keep the array sorted, we need to place at 1 so dp=[-1,4,5,6]. current arr=[1,7,8,4,5,6,-1] so LIS=[1,4,5,6] whose lenght is same as our dp table so make sense. dp=[-1,4,5,6]

at i=7, element=9, we can push 9 at the end to maintain the sorted order, so dp=[-1,4,5,6,9]. our current arr=[1,7,8,4,5,6,-1,9] so LIS=[1,4,5,6,9] whose lenght is same as our dp arr.

so even if the order is elements in the dp table is not right, our lenght of LIS is making sense.
why replacing -1 with the 1 ath i=6, because it will take care of those subsequence also which will start from -1, suppose 2,3,4,5,6 comes when suppose our dp was [-1,40,50,60] so our dp will become [-1,2,3,4,5,6] as per our process, so we get to see that possibility also.

at the i=7, techincally LIS=[1,4,5,6,9] but our dp has [-1,4,5,6,9], here -1 will actually 1 only but it is not disturbing our the LIS lenght finding algo.

just use the left_bisect to find the left index to push the elment.

'''
from bisect import bisect_left
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        arr=[] #LIS not the elements, just to tract the lengths
        for i in nums:
            if arr and arr[-1]>=i:
                ind=bisect_left(arr,i)
                arr[ind]=i
            else:
                arr.append(i) #This way you are replacing so number will still be same for eg [10,12,14,16] and then 8 came so now it will [8,12,14,16] but number is still 4 only that was actually the answer too
        return len(arr)