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