企业官网建设流程全解析

LeetCode 300 & 674：最长递增子序列 vs 最长连续递增子序列 —— 联合题解 ✅

这两道题名字几乎一样，但DP 思想和难度完全不同。
下面我把它们放在一张笔记里，重点对比“连续 vs 不连续”。

📌 题目列表

📖 内容概要

给定一个整数数组nums，求最长递增子序列的长度。

• 300：可以不连续
• 674：必须连续

✅ 动态规划
✅ 面试高频
✅ 对比强烈

💡 解题思路对比（核心）

一、状态定义（两题相同）

dp[i]=以 nums[i]结尾的递增子序列长度

二、状态转移（关键区别）

✅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;}}

复杂度

✅ 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;}}

复杂度

🔍 两题核心对比总结

✅ 一句话总结

300 是“选或不选”的 DP，674 是“接或不接”的 DP。

📌 面试加分点（建议记住）

• ✅ 为什么 300 不能贪心？
• ✅ 为什么 674 不需要二维 DP？
• ✅ 什么时候可以用贪心代替 DP？
• ✅ 如何把 300 优化到 O(n log n)