Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:


Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. 

Note: 


       There may be more than one LIS combination, it is only necessary for you to return the length.
       Your algorithm should run in O(n2) complexity.


Follow up: Could you improve it to O(n log n) time complexity?

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Sorting

Data structures

Starter code: class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        

Solutions:
class Solution:

	def lengthOfLIS(self, nums):
		if len(nums) == 0:
			return 0
		res = [nums[0]]

		def binarySearch(l, target):
			(left, right) = (0, len(l) - 1)
			while left < right:
				mid = (left + right) // 2
				if l[mid] >= target:
					right = mid
				else:
					left = mid + 1
			return left
		for i in range(1, len(nums)):
			if nums[i] > res[-1]:
				res.append(nums[i])
			else:
				res[binarySearch(res, nums[i])] = nums[i]
		return len(res)


class Solution:

	def lengthOfLIS(self, nums):
		if not nums:
			return 0
		c = [nums[0]]
		for i in range(1, len(nums)):
			if nums[i] <= c[0]:
				c[0] = nums[i]
				continue
			if nums[i] > c[-1]:
				c.append(nums[i])
				continue
			l = 0
			h = len(c) - 1
			while l + 1 != h:
				m = l + h >> 1
				if nums[i] > c[m]:
					l = m
				else:
					h = m
			c[h] = nums[i]
		return len(c)


class Solution:

	def lengthOfLIS(self, nums):
		tails = [0] * len(nums)
		size = 0
		for num in nums:
			(i, j) = (0, size)
			while i != j:
				m = i + (j - i) // 2
				if tails[m] < num:
					i = m + 1
				else:
					j = m
			tails[i] = num
			size = max(i + 1, size)
		return size


class Solution:

	def lengthOfLIS(self, nums):
		n = len(nums)
		dp = [float('inf')] * (n + 1)
		res = 0
		for num in nums:
			(lo, hi) = (1, n)
			while lo < hi:
				mi = int((lo + hi) / 2)
				if dp[mi] < num:
					lo = mi + 1
				else:
					hi = mi
			dp[lo] = num
			res = max(res, lo)
		return res


class Solution:

	def lengthOfLIS(self, nums):
		tails = []
		size = 0

		def search_tails(tails, n):
			if len(tails) == 0:
				return 0
			(l, r) = (0, len(tails))
			while l < r:
				m = (l + r) // 2
				if tails[m] < n:
					l = m + 1
				else:
					r = m
			return l
		for n in nums:
			i = search_tails(tails, n)
			if i == len(tails):
				tails.append(n)
			else:
				tails[i] = n
		return len(tails)


class Solution:

	def lengthOfLIS(self, nums):
		maxLen = 0
		dp = []
		for i in nums:
			if not dp:
				dp.append(i)
			pos = self.search(i, dp)
			if pos == len(dp):
				dp.append(i)
			else:
				dp[pos] = i
			maxLen = max(maxLen, len(dp))
		return maxLen

	def search(self, curr, nums):
		start = 0
		end = len(nums) - 1
		if curr > nums[-1]:
			return len(nums)
		while end >= start:
			mid = int(start + (end - start) / 2)
			if curr < nums[mid]:
				end = mid - 1
			elif curr > nums[mid]:
				start = mid + 1
			else:
				return mid
		return start


class Solution:

	def lengthOfLIS(self, nums):
		tails = [0] * len(nums)
		size = 0
		for x in nums:
			i = 0
			j = size
			index_to_insert = i
			while i < j:
				mid = i + (j - i) // 2
				if tails[mid] < x:
					i = mid + 1
				else:
					j = mid
			tails[i] = x
			size = max(size, i + 1)
		return size


class Solution:

	def lengthOfLIS(self, nums):
		n = len(nums)
		if n <= 1:
			return n
		tails = [nums[0]]
		for i in range(1, n):
			x = nums[i]
			(l, r) = (0, len(tails) - 1)
			while l < r:
				mid = (l + r) // 2
				if tails[mid] >= x:
					r = mid
				else:
					l = mid + 1
			if tails[l] < x:
				tails.append(x)
			else:
				tails[l] = x
		return len(tails)


class Solution:

	def lengthOfLIS(self, nums):
		import bisect
		d = [0] * len(nums)
		maxLen = 0
		for n in nums:
			i = bisect.bisect_left(d, n, 0, maxLen)
			if i == maxLen:
				maxLen += 1
			d[i] = n
		return maxLen


class Solution:

	def lengthOfLIS(self, nums):
		if nums == []:
			return 0
		dp = []
		for (i, num) in enumerate(nums):
			if i == 0 or num > dp[-1]:
				dp.append(num)
			elif num < dp[0]:
				dp[0] = num
			else:
				(low, high) = (0, len(dp) - 1)
				while low < high:
					mid = (low + high) // 2
					mid_num = dp[mid]
					if num > mid_num:
						low = mid + 1
					else:
						high = mid
				dp[low] = num
		return len(dp)


class Solution:

	def lengthOfLIS(self, nums):
		lenLastIdx = [-1]
		for i in range(len(nums)):
			currLen = self.findLen(nums, lenLastIdx, nums[i])
			if len(lenLastIdx) == currLen:
				lenLastIdx.append(0)
			lenLastIdx[currLen] = i
		return len(lenLastIdx) - 1

	def findLen(self, nums, lenLastIdx, val):
		p = 1
		q = len(lenLastIdx)
		while p < q:
			mid = p + (q - p) // 2
			if nums[lenLastIdx[mid]] >= val:
				q = mid
			else:
				p = mid + 1
		return p