企业官网建设流程全解析

目录

一、300. 最长递增子序列

题目回顾

思路复盘

方法 1：基础动态规划（O (n²)）

方法 2：二分查找优化（O (n log n)）

易错点 & 二刷心得

二、152. 乘积最大子数组

题目回顾

思路复盘

核心思路：同时维护最大值和最小值

易错点 & 二刷心得

三、两道题的共性总结 & 二刷收获

这两道题都是中等难度的经典动态规划题，第一次刷的时候很容易踩坑，二刷时我们重点拆解思路、优化写法，顺便把易错点和通用模板总结清楚。

一、300. 最长递增子序列

题目回顾

给你一个整数数组nums，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。

思路复盘

方法 1：基础动态规划（O (n²)）

这是最直观的解法，核心是定义状态和状态转移方程。

1. 状态定义：dp[i]表示以nums[i]结尾的最长递增子序列的长度。
2. 状态转移：
   • 对于每个i，遍历j ∈ [0, i-1]
   • 如果nums[i] > nums[j]，说明可以把nums[i]接在nums[j]后面，形成更长的递增子序列
   • 状态转移方程：dp[i] = max(dp[i], dp[j] + 1)
3. 初始状态：每个元素本身都是长度为 1 的子序列，所以dp[i] = 1
4. 结果：dp数组中的最大值

Java 代码实现

java

运行

public int lengthOfLIS(int[] nums) { if (nums == null || nums.length == 0) return 0; int n = nums.length; int[] dp = new int[n]; Arrays.fill(dp, 1); int maxLen = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } maxLen = Math.max(maxLen, dp[i]); } return maxLen; }

方法 2：二分查找优化（O (n log n)）

进阶优化思路，用一个数组维护最小结尾元素：

• tails[i]表示长度为i+1的递增子序列的最小可能结尾元素
• 遍历nums，对每个元素num：
  1. 如果num大于tails最后一个元素，直接追加到末尾，子序列长度 + 1
  2. 否则，用二分查找找到tails中第一个大于等于num的位置，替换它（保证后续有更长的递增可能）
• 最终tails的长度就是最长递增子序列的长度

Java 代码实现

java

运行

public int lengthOfLIS(int[] nums) { if (nums == null || nums.length == 0) return 0; int[] tails = 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 (tails[mid] < num) { left = mid + 1; } else { right = mid; } } tails[left] = num; if (left == len) { len++; } } return len; }

易错点 & 二刷心得

1. DP 方法的边界：dp数组的初始值必须全为 1，因为每个元素本身就是一个子序列。
2. 二分方法的误区：tails数组并不是最终的最长递增子序列，它只是维护了最小结尾，长度才是答案。
3. 适用场景：O (n²) 适合数据量较小的场景，O (n log n) 是面试中的进阶优化点，建议两种方法都掌握。

二、152. 乘积最大子数组

题目回顾

给你一个整数数组nums，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

思路复盘

这道题和「最大子数组和」很像，但因为负数和 0 的存在，直接用单变量 DP 会翻车：负数乘以负数会变成正数，之前的最小值可能变成最大值。

核心思路：同时维护最大值和最小值

1. 状态定义：
   • maxDp[i]：以nums[i]结尾的子数组的最大乘积
   • minDp[i]：以nums[i]结尾的子数组的最小乘积（因为负负得正，最小值可能变成最大值）
2. 状态转移：
   • 对于每个nums[i]，有三种选择：
     1. 只取当前元素nums[i]
     2. 用之前的最大值乘当前元素：maxDp[i-1] * nums[i]
     3. 用之前的最小值乘当前元素：minDp[i-1] * nums[i]
   • 状态转移方程：

     plaintext

     maxDp[i] = max(nums[i], maxDp[i-1] * nums[i], minDp[i-1] * nums[i]) minDp[i] = min(nums[i], maxDp[i-1] * nums[i], minDp[i-1] * nums[i])

3. 初始状态：maxDp[0] = minDp[0] = nums[0]
4. 结果：遍历过程中记录的最大值

Java 代码实现（优化空间版）

java

运行

public int maxProduct(int[] nums) { if (nums == null || nums.length == 0) return 0; int max = nums[0], min = nums[0], result = nums[0]; for (int i = 1; i < nums.length; i++) { // 保存之前的max，避免被覆盖 int prevMax = max; int prevMin = min; max = Math.max(nums[i], Math.max(prevMax * nums[i], prevMin * nums[i])); min = Math.min(nums[i], Math.min(prevMax * nums[i], prevMin * nums[i])); result = Math.max(result, max); } return result; }

易错点 & 二刷心得

1. 为什么要同时维护最小值？比如nums = [-2, 3, -4]，第一次计算到 3 时，最小值是 - 6，第二次乘以 - 4，得到 24，这就是最大值。
2. 空间优化技巧：不需要完整的dp数组，只需要用两个变量保存上一次的最大值和最小值即可，空间复杂度从 O (n) 降到 O (1)。
3. 0 的处理：当遇到 0 时，max 和 min 都会被重置为 0，后续计算会重新开始，不影响结果。

三、两道题的共性总结 & 二刷收获

1. 动态规划的核心：定义清晰的状态、找到正确的状态转移方程，这是解决 DP 题的关键。
2. 特殊情况的处理：
   • 最长递增子序列：二分优化的核心是维护最小结尾，这是贪心 + 二分的经典结合。
   • 乘积最大子数组：必须同时维护最大和最小值，应对负数带来的反转问题。
3. 优化意识：二刷时要从暴力解法出发，思考如何优化时间 / 空间复杂度，比如把 O (n²) 降到 O (n log n)，把 O (n) 空间降到 O (1)。