LeetCode300给你一个整数数组nums找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。示例 1输入nums [10,9,2,5,3,7,101,18]输出4解释最长递增子序列是 [2,3,7,101]因此长度为 4 。示例 2输入nums [0,1,0,3,2,3]输出4Python解法1.动态规划class Solution: def lengthOfLIS(self, nums: List[int]) - int: if len(nums) 0: return 0 dp [1] * len(nums) for i in range(len(nums)): for j in range(i): if nums[i] nums[j]: dp[i] max(dp[i], dp[j] 1) return max(dp)2.贪心二分class Solution: def lengthOfLIS(self, nums: List[int]) - int: d [] for num in nums: # 直接二分查找第一个 num 的位置 left, right 0, len(d) while left right: mid (left right) // 2 if d[mid] num: right mid else: left mid 1 # left就是要替换的下标 if left len(d): d.append(num) else: d[left] num return len(d)Java解法1.动态规划class Solution { public int lengthOfLIS(int[] nums) { if(nums.length 0) return 0; int[] dp new int[nums.length]; for(int i 0; i nums.length; i){ dp[i] 1; } int res 1; for(int i 0; i nums.length; i){ for(int j 0; j i; j){ if(nums[i] nums[j]){ dp[i] Math.max(dp[i], dp[j] 1); } } res Math.max(res, dp[i]); } return res; } }2.贪心二分class Solution { public int lengthOfLIS(int[] nums) { int[] d new int[nums.length]; int len 0; for (int num : nums) { int left 0, right len; while (left right) { int mid (left right) / 2; if (d[mid] num) { right mid; } else { left mid 1; } } if (left len) { d[len] num; } else { d[left] num; } } return len; } }C解法1.动态规划class Solution { public: int lengthOfLIS(vectorint nums) { int n nums.size(); if(n 0)return 0; vectorint dp(n, 1); // 初始化dp数组所有元素初始值为1 for (int i 0; i n; i) { // 遍历i之前所有元素 j ∈ [0, i-1] for (int j 0; j i; j) { if (nums[i] nums[j]) { dp[i] max(dp[i], dp[j] 1); } } } // 返回dp数组最大值 return *max_element(dp.begin(), dp.end()); } };2.贪心二分class Solution { public: int lengthOfLIS(vectorint nums) { vectorint d; for (int num : nums) { int left 0, right d.size(); while (left right) { int mid (left right) / 2; if (d[mid] num) { right mid; } else { left mid 1; } } if (left d.size()) { d.push_back(num); } else { d[left] num; } } return d.size(); } };一、动态规划 DP原理拆分成小问题存下每个小问题的最优解避免重复计算靠前面结果推出当前结果满足最优子结构、重叠子问题、无后效性。LIS 里的表现dp[i]以第 i 个数结尾的最长递增子序列长度逐个对比前面所有数字更新。复杂度\(O(n^2)\)适合题目数据量小n≤1000需要输出完整子序列、统计有多少条最长序列背包、最长公共子序列 LCS、打家劫舍、股票问题贪心做不了。二、贪心 二分LIS 优化版原理贪心相同长度的递增子序列末尾数字越小后续越好接更大数字二分快速找到要替换的位置把时间压到对数级。LIS 里的表现数组 dd [k] 代表长度 k1 的序列最小末尾值新数字要么加长序列要么替换旧末尾。复杂度\(O(n\log n)\)适合题目数据量大n 上万 / 十万只需要求最长序列长度不需要路径、计数导弹拦截、俄罗斯套娃信封。极简区分DP万能能计数 / 找路径慢小数组用贪心二分只算长度速度极快大数据专用。