Given an array of integers, find the length of the longest (strictly) increasing subsequence from the given array.
Example 1:
Input:
N = 16
A[]={0,8,4,12,2,10,6,14,1,9,5
     13,3,11,7,15}
Output: 6
Explanation:Longest increasing subsequence
0 2 6 9 13 15, which has length 6
Example 2:
Input:
N = 6
A[] = {5,8,3,7,9,1}
Output: 3
Explanation:Longest increasing subsequence
5 7 9, with length 3
Your Task:
Complete the function longestSubsequence() which takes the input array and its size as input parameters and returns the length of the longest increasing subsequence.
Expected Time Complexity : O( N*log(N) )
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{4}
0 ≤ A[i] ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:
    
    #Function to find length of longest increasing subsequence.
    def longestSubsequence(self,a,n):
        # code here
       


Solutions:
class Solution:

	def longestSubsequence(self, a, n):
		dp = [float('inf')] * (n + 1)
		dp[0] = float('-inf')
		max_len = 0
		for num in a:
			left = 0
			right = max_len
			while left <= right:
				mid = (left + right) // 2
				if dp[mid] < num:
					left = mid + 1
				else:
					right = mid - 1
			dp[left] = num
			max_len = max(max_len, left)
		return max_len


import bisect

class Solution:

	def longestSubsequence(self, arr, n):
		a = []
		if n == 0:
			return 0
		a.append(arr[0])
		for i in range(1, n):
			if arr[i] > a[len(a) - 1]:
				a.append(arr[i])
			else:
				ind = bisect.bisect_left(a, arr[i])
				a[ind] = arr[i]
		return len(a)


from bisect import bisect_left

class Solution:

	def longestSubsequence(self, arr, n):
		seq = []
		for a in arr:
			i = bisect_left(seq, a)
			if i == len(seq):
				seq.append(a)
			else:
				seq[i] = a
		return len(seq)


import bisect

class Solution:

	def longestSubsequence(self, a, n):
		if n == 0:
			return 0
		ans = [a[0]]
		for i in range(1, n):
			if a[i] > ans[-1]:
				ans.append(a[i])
			else:
				index = bisect.bisect_left(ans, a[i])
				ans[index] = a[i]
		return len(ans)