两道经典子序列 / 子数组 DP 题：最长递增子序列 乘积最大子数组

前言动态规划里「子序列」和「子数组」是高频考点很多同学容易把它们搞混。今天我们就用两道中等难度的经典题把这两个概念和对应的 DP 解法讲透一道是 **《最长递增子序列》一道是《乘积最大子数组》**。一、最长递增子序列LeetCode 300题目描述给你一个整数数组nums找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。核心思路一维 DP 优化这道题是子序列 DP 的入门标杆题核心是通过「前序状态」推导出当前状态。状态定义dp[i]表示以nums[i]结尾的最长递增子序列的长度。转移方程对于每个i遍历所有j i如果nums[i] nums[j]则dp[i] max(dp[i], dp[j] 1)边界条件每个元素自身都是一个长度为 1 的子序列所以dp[i]初始化为 1最终答案是dp数组中的最大值代码实现Java 版java运行public class LengthOfLIS { // 基础DP解法O(n²) 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; } // 优化解法贪心二分O(n log n) public int lengthOfLISOptimized(int[] nums) { ListInteger tails new ArrayList(); for (int num : nums) { // 找到第一个 num 的位置替换为 num int idx Collections.binarySearch(tails, num); if (idx 0) idx -idx - 1; if (idx tails.size()) { tails.add(num); } else { tails.set(idx, num); } } return tails.size(); } public static void main(String[] args) { LengthOfLIS solution new LengthOfLIS(); int[] nums {10,9,2,5,3,7,101,18}; System.out.println(solution.lengthOfLIS(nums)); // 输出4 System.out.println(solution.lengthOfLISOptimized(nums)); // 输出4 } }关键知识点时间复杂度基础 DP 为 O (n²)优化后为 O (n log n)空间复杂度基础 DP 为 O (n)优化后为 O (n)核心区别子序列不要求连续所以需要遍历所有前序元素而不是只看相邻元素二、乘积最大子数组LeetCode 152题目描述给你一个整数数组nums请你找出数组中乘积最大的非空连续子数组该子数组中至少包含一个数字并返回该子数组所对应的乘积。核心思路维护最大 / 最小值的 DP这道题的坑点在于负数负负得正所以当前的最小值负数乘以一个负数反而可能变成最大值。因此我们不能只维护当前的最大值还要维护当前的最小值。状态定义maxDp[i]以nums[i]结尾的乘积最大子数组的乘积minDp[i]以nums[i]结尾的乘积最小子数组的乘积转移方程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])边界条件maxDp[0] minDp[0] nums[0]最终答案是maxDp数组中的最大值代码实现Java 版java运行public class MaxProduct { // 基础DP解法 public int maxProduct(int[] nums) { if (nums null || nums.length 0) return 0; int n nums.length; int[] maxDp new int[n]; int[] minDp new int[n]; maxDp[0] minDp[0] nums[0]; int maxRes nums[0]; for (int i 1; i n; i) { maxDp[i] Math.max(nums[i], Math.max(maxDp[i-1] * nums[i], minDp[i-1] * nums[i])); minDp[i] Math.min(nums[i], Math.min(maxDp[i-1] * nums[i], minDp[i-1] * nums[i])); maxRes Math.max(maxRes, maxDp[i]); } return maxRes; } // 优化版空间O(1) public int maxProductOptimized(int[] nums) { if (nums null || nums.length 0) return 0; int max nums[0], min nums[0], res nums[0]; for (int i 1; i nums.length; i) { int currMax Math.max(nums[i], Math.max(max * nums[i], min * nums[i])); int currMin Math.min(nums[i], Math.min(max * nums[i], min * nums[i])); max currMax; min currMin; res Math.max(res, max); } return res; } public static void main(String[] args) { MaxProduct solution new MaxProduct(); int[] nums {2,3,-2,4}; System.out.println(solution.maxProduct(nums)); // 输出6 System.out.println(solution.maxProductOptimized(nums)); // 输出6 } }关键知识点时间复杂度O (n)仅遍历一次数组空间复杂度基础 DP 为 O (n)优化后为 O (1)核心区别子数组必须连续所以只需要看前一个状态而不是所有前序状态