Longest Increasing Subsequence O(nlog n) O(n**2)

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n=len(nums)
        lis=[1]*n
        lis[-1]=1
        for i in range(n-1,-1,-1):
            for j in range(i+1,n):
                if nums[i]<nums[j]:
                    lis[i]=max(lis[i],1+lis[j])
                '''
                Dont write this else.
                Because Once you update lis[i] it will affect the ones of lis[1...i] and give wrong solutions
                else:
                    lis[i]=max(lis[i],lis[j])
                '''
        return max(lis)
from bisect import bisect_left as bs
class Solution:

    #Function to find length of longest increasing subsequence.
    def longestSubsequence(self,a,n):
        ans=[]
        for i in a:
            if not ans or ans[-1]<i:ans.append(i)
            t=bs(ans,i)
            ans[t]=i
        return len(ans)