LeetCode 300 Longest Increasing Subsequence

LeetCode

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Example 1:

Input: nums = [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.

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints:

1 <= nums.length <= 2500 -10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

DP算法思路：

N/A

注意事项：

1. 初始化从1开始，因为一个数是递增序列
2. 返回值不是dp[-1]，而是所有dp的最大值

Python代码：

[3, 5, 1, 3, 9, 5, 6] 1, 3, 5, 6
[1, 0]
dp[i] = max(dp[j]) + 1, if nums[i-1] > nums[j-1], 1 <= j < i
	
def lengthOfLIS(self, nums: List[int]) -> int:
	if not nums:
		return 0
	res = 1
	# dp = [0, 1, 0]
	dp = [1] * (len(nums) + 1)
	for i in range(1, len(dp)):
		# i = 2
		# j = 1
		for j in range(1, i):
			if nums[i - 1] > nums[j - 1]:
				dp[i] = max(dp[i], dp[j] + 1)
		res = max(res, dp[i])
	return res

算法分析：

时间复杂度为O(n2)，空间复杂度O(n2).

---

打印路径算法思路：

N/A

注意事项：

1. path数组大小和原数组一样，因为path数组的下标和值都是下标，这样不用-1，直接nums[pos]，不容易错
2. 多了Line 11 - 12和14 - 15，需要记录产生最大值的下标
3. 打印的时候path数组的下标和值都是下标，而值是前一个下标，所以是pos = positions[pos]，循环次数为dp值，开始下标为dp值对应的下标path[:biggest_pos + 1]。

Python代码：

def lengthOfLIS_with_path(self, nums: List[int]) -> int:
	if not nums:
		return 0
	res, path = 1, [0] * len(nums)  # remember no + 1
	biggest_pos = -1
	dp = [1] * (len(nums) + 1)
	for i in range(1, len(dp)):
		for j in range(1, i):
			if nums[i - 1] > nums[j - 1]:
				dp[i] = max(dp[i], dp[j] + 1)
				if dp[i] == dp[j] + 1:
					path[i - 1] = j - 1
		res = max(res, dp[i])
		if res == dp[i]:
			biggest_pos = i - 1
	path_list = self.print_path(nums, path[:biggest_pos + 1], res)
	return path_list

def print_path(self, nums, path, dp_value):
	pos, res = len(path) - 1, []
	for _ in range(dp_value):
		res.append(nums[pos])
		pos = path[pos]
	return res[::-1]

---

bisect算法II解题思路：

N/A

注意事项：

1. bisect_left类似于greater_or_equal_position但若equal时，取第一个，但greater_or_equal_position是取最后一个，此题没关系，因为相等的数会被替换掉，递增序列中不会存在相等的数

Python代码：

def lengthOfLIS(self, nums: List[int]) -> int:
	if not nums:
		return 0
	res = []
	for i in range(len(nums)):
		pos = bisect.bisect_left(res, nums[i])
		if pos < len(res):
			res[pos] = nums[i]
		else:
			res.append(nums[i])
	return len(res)

算法分析：

时间复杂度为O(nlogn)，空间复杂度O(n).