动态规划经典题解：最长递增子序列 乘积最大子数组

目录一、最长递增子序列LIS题目描述思路分析1. 动态规划解法基础版2. 优化解法贪心 二分代码实现Java二、乘积最大子数组题目描述思路分析代码实现Java三、两道题的核心对比与面试考点四、总结大家好今天我们来拆解两道动态规划的经典中等难度题目最长递增子序列和乘积最大子数组。这两道题都是大厂面试里的高频考点而且非常能体现动态规划的核心思想 —— 如何通过子问题的最优解一步步推导出全局最优解。一、最长递增子序列LIS题目描述给你一个整数数组nums找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。思路分析1. 动态规划解法基础版定义状态dp[i]表示以nums[i]结尾的最长递增子序列的长度。状态转移方程对于每个i遍历0到i-1的所有j如果nums[i] nums[j]则dp[i] max(dp[i], dp[j] 1)。初始状态每个元素自身都是一个长度为 1 的子序列所以dp[i] 1。结果dp数组中的最大值就是整个数组的最长递增子序列长度。2. 优化解法贪心 二分动态规划的时间复杂度是 O(n2)我们可以用贪心 二分将复杂度优化到 O(nlogn)。维护一个数组tails其中tails[k]表示长度为k1的最长递增子序列的最小可能的末尾元素。遍历nums中的每个数x如果x大于tails最后一个元素直接追加到tails末尾否则找到tails中第一个大于等于x的位置替换为x。最终tails的长度就是 LIS 的长度。代码实现Javajava运行// 动态规划 O(n²) 版本 public int lengthOfLIS(int[] nums) { if (nums null || nums.length 0) return 0; int[] dp new int[nums.length]; Arrays.fill(dp, 1); int maxLen 1; for (int i 1; i nums.length; 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 lengthOfLISOpt(int[] nums) { if (nums null || nums.length 0) return 0; ListInteger tails new ArrayList(); for (int x : nums) { if (tails.isEmpty() || x tails.get(tails.size() - 1)) { tails.add(x); } else { // 二分查找第一个 x 的位置 int left 0, right tails.size() - 1; while (left right) { int mid (left right) / 2; if (tails.get(mid) x) { right mid; } else { left mid 1; } } tails.set(left, x); } } return tails.size(); }二、乘积最大子数组题目描述给你一个整数数组nums请你找出数组中乘积最大的非空连续子数组该子数组中至少包含一个数字并返回该子数组所对应的乘积。思路分析这道题和经典的「最大子数组和」很像但乘积有个特殊的问题负数的存在会让最小值变成最大值。比如当前是-2后面跟着一个-3那么-2 * -3 6就会变成正数比之前的正数乘积更大。定义状态maxDp[i]以nums[i]结尾的最大乘积子数组的乘积。minDp[i]以nums[i]结尾的最小乘积子数组的乘积。状态转移方程plaintextmaxDp[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])因为nums[i]可能是负数乘以之前的最小值反而可能得到最大值所以必须同时维护最大和最小值。初始状态maxDp[0] minDp[0] nums[0]。结果遍历maxDp数组取最大值即可。代码实现Javajava运行public int maxProduct(int[] nums) { if (nums null || nums.length 0) return 0; int n nums.length; int maxDp nums[0]; int minDp nums[0]; int result nums[0]; for (int i 1; i n; i) { // 必须先保存避免被覆盖 int currMax maxDp; int currMin minDp; maxDp Math.max(nums[i], Math.max(currMax * nums[i], currMin * nums[i])); minDp Math.min(nums[i], Math.min(currMax * nums[i], currMin * nums[i])); result Math.max(result, maxDp); } return result; }三、两道题的核心对比与面试考点表格题目核心难点优化技巧面试常见追问最长递增子序列如何定义状态、如何优化时间复杂度贪心 二分将 O(n2) 优化到 O(nlogn)请输出最长递增子序列本身而不是长度乘积最大子数组负数导致的 “最大 / 最小值反转” 问题同时维护max和min两个状态变量如果数组全是负数怎么处理如果包含 0 呢四、总结最长递增子序列基础版 DP 是理解动态规划状态定义和转移的绝佳例子。优化版的贪心 二分体现了如何用额外的空间和更高效的算法突破 DP 的时间复杂度瓶颈。乘积最大子数组核心是打破思维定势不像 “最大子数组和” 只维护一个最大值而是要同时维护最大和最小值因为负数的存在会让最小值变成最大值。