最长上升序列,找出nums中的最长严格单增子序列
类似于Leetcode 300 最长公共序列
状态表示
- 集合:dp[i] 代表以第i个数作为终结点的所有严格递增序列的长度
- 属性:max, 集合中“最大”长度
状态计算
- 状态划分: 以序列倒数第二个数字作为划分
- 递归公式: dp[i] = max({dp[j]}) + 1
- 限制条件: 0<=j<i, nums[j] < nums[i]
优化
- g[i]下标代表nums[i]的dp值, 数值代表nums[i]
- 贪心思想:以idx=4为例,3能插入到-1后面也必然能插入到-4后面,所以总是保留相同dp值的集合中的最小nums[idx]
- g的单调性证明(要想利用二分搜索, aux必须是单调的)
g的单调性证明(要想利用二分搜索, g必须是单调的)
假设g前i位严格单增, 但g[i] >= g[i+1]
证明:因为g[i] >= g[i+1] ,但最长递增子序列构成的树中, g[i+1]肯定插入到一个小于g[i+1]的数j后面构成最长递增子序列, j和g[i]的dp值相同但j<g[i], 与g[i]的定义矛盾
所以当g前i位单增, 必有g[i] < g[i+1]
#优化前 动态规划#
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums: return 0
n = len(nums)
f = [1 for i in range(n)]
for i in range(1,n):
maxf = -sys.maxsize
for j in range(i-1,-1,-1):
if nums[i] > nums[j]:
maxf = max(f[j], maxf)
f[i] = maxf + 1 if maxf != -sys.maxsize else 1
return max(f)
#优化后 贪心算法#
class Solution:
def bs(self, nums, num, length): #二分搜索, 下位分界点
l , r = 0, length
while l < r:
mid = l + r + 1 >> 1
if nums[mid] < num:
l = mid
else:
r = mid -1
return l
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums: return 0
n = len(nums)
g = [0 for i in range(n+1)] #下标是f, 数值代表相同f时最小的nums[i]
g[0] = -sys.maxsize-1 #二分搜索的哨兵
length = 0 #代表g的有效长度
for i in range(n):
idx = self.bs(g, nums[i], length)
g[idx + 1] = nums[i] #此时必有 num[i] <= g[idx+1]
length = max(idx + 1, length)
return length