【重点】【DP】300.最长递增子序列

题目
参考两个题目：
300.最长递增子序列
354. 俄罗斯套娃信封问题

Python

法1：动态规划

classSolution:deflengthOfLIS(self,nums:List[int])->int:n=len(nums)dp=[1]*n max_len=1foriinrange(n):forjinrange(i):ifnums[j]<nums[i]:dp[i]=max(dp[i],dp[j]+1)max_len=max(max_len,dp[i])returnmax_len

法2：二分+谈心

frombisectimportbisect_left# 在力扣中不用importclassSolution:deflengthOfLIS(self,nums:List[int])->int:arr=[]# dp[i]表示长度为i+1的最小元素forxinnums:idx=bisect_left(arr,x)ifidx==len(arr):arr.append(x)else:arr[idx]=xreturnlen(arr)

补充获取最长递增子序列

classSolution:deflengthOfLIS(self,nums:List[int])->List[int]:ifnotnums:return[]n=len(nums)dp=[1]*n# dp[i] 表示以 nums[i] 结尾的 LIS 长度prev=[-1]*n# 前驱索引# 计算 dp 和 prevforiinrange(n):forjinrange(i):ifnums[j]<nums[i]anddp[j]+1>dp[i]:dp[i]=dp[j]+1prev[i]=j# 找到最大长度的结尾索引max_len=max(dp)end_idx=dp.index(max_len)# 重建序列lis=[]curr=end_idxwhilecurr!=-1:lis.append(nums[curr])curr=prev[curr]returnlis[::-1]

Java

法1：DP

必须掌握，O(N^2) + O(N)

classSolution{publicintlengthOfLIS(int[]nums){int[]dp=newint[nums.length];Arrays.fill(dp,1);intres=1;for(inti=1;i<nums.length;++i){for(intj=0;j<i;++j){if(nums[i]>nums[j]){dp[i]=Math.max(dp[i],dp[j]+1);}}res=res>dp[i]?res:dp[i];}returnres;}}

法2：二分搜索

O(NlgN) + O(N)
patience sorting（耐心排序），参考《算法小抄》p100，介绍详细！