<div>
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:
<pre>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. </pre>
Example 2:
<pre>Input: nums = [0,1,0,3,2,3] Output: 4 </pre>
Example 3:
<pre>Input: nums = [7,7,7,7,7,7,7] Output: 1 </pre>
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?
</div>
DP算法思路：
N/A
注意事项：
- 初始化从1开始，因为一个数是递增序列
- 返回值不是dp[-1]，而是所有dp的最大值
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18[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
算法分析：
时间复杂度为<code>O(n<sup>2</sup>)</code>，空间复杂度<code>O(n<sup>2</sup>)</code>.
打印路径算法思路：
N/A
注意事项：
- path数组大小和原数组一样，因为path数组的下标和值都是下标，这样不用-1，直接nums[pos]，不容易错
- 多了Line 11 - 12和14 - 15，需要记录产生最大值的下标
- 打印的时候path数组的下标和值都是下标，而值是前一个下标，所以是pos = positions[pos]，循环次数为dp值，开始下标为dp值对应的下标path[:biggest_pos + 1]。
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24def 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
注意事项：
- bisect_left类似于greater_or_equal_position但若equal时，取第一个，但greater_or_equal_position是取最后一个，此题没关系，因为相等的数会被替换掉，递增序列中不会存在相等的数
Python代码：
1
2
3
4
5
6
7
8
9
10
11def 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).
