LeetCode 300 674：最长递增子序列 vs 最长连续递增子序列

LeetCode 300 674最长递增子序列 vs 最长连续递增子序列 —— 联合题解 ✅这两道题名字几乎一样但DP 思想和难度完全不同。下面我把它们放在一张笔记里重点对比“连续 vs 不连续”。 题目列表题号题目是否连续300最长递增子序列❌ 不要求连续674最长连续递增子序列✅ 必须连续 内容概要给定一个整数数组nums求最长递增子序列的长度。300可以不连续674必须连续✅ 动态规划✅ 面试高频✅ 对比强烈 解题思路对比核心一、状态定义两题相同dp[i]以 nums[i]结尾的递增子序列长度二、状态转移关键区别题目状态转移300dp[i] max(dp[j] 1) , j i nums[i] nums[j]674dp[i] dp[i-1] 1 , nums[i] nums[i-1]✅300 要枚举所有前面的 j✅674 只看前一个✅ 300 题最长递增子序列不连续思路每个位置尝试接在所有更小的数后面取最大值AC 代码JavaclassSolution{publicintlengthOfLIS(int[]nums){intlennums.length;int[]dpnewint[len];intres1;for(inti0;ilen;i){dp[i]1;for(intj0;ji;j){if(nums[i]nums[j]){dp[i]Math.max(dp[i],dp[j]1);}}resMath.max(res,dp[i]);}returnres;}}复杂度指标复杂度时间复杂度O(n²)空间复杂度O(n)✅ 674 题最长连续递增子序列思路只关心是否比前一个大是 → 续上否 → 重新开始AC 代码JavaclassSolution{publicintfindLengthOfLCIS(int[]nums){intlennums.length;int[]dpnewint[len];intres1;dp[0]1;for(inti1;ilen;i){if(nums[i]nums[i-1]){dp[i]dp[i-1]1;}else{dp[i]1;}resMath.max(res,dp[i]);}returnres;}}复杂度指标复杂度时间复杂度O(n)空间复杂度O(n) 两题核心对比总结对比项300674是否连续❌✅状态依赖所有前面状态仅前一个时间复杂度O(n²)O(n)难度中等简单✅ 一句话总结300 是“选或不选”的 DP674 是“接或不接”的 DP。 面试加分点建议记住✅ 为什么 300 不能贪心✅ 为什么 674 不需要二维 DP✅ 什么时候可以用贪心代替 DP✅ 如何把 300 优化到 O(n log n)