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

目录

一、最长递增子序列（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]表示长度为k+1的最长递增子序列的最小可能的末尾元素。
• 遍历nums中的每个数x：
  • 如果x大于tails最后一个元素，直接追加到tails末尾；
  • 否则，找到tails中第一个大于等于x的位置，替换为x。
• 最终tails的长度就是 LIS 的长度。

代码实现（Java）

java

运行

// 动态规划 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; List<Integer> 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]结尾的最小乘积子数组的乘积。
• 状态转移方程：

  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])

  因为nums[i]可能是负数，乘以之前的最小值反而可能得到最大值，所以必须同时维护最大和最小值。
• 初始状态：maxDp[0] = minDp[0] = nums[0]。
• 结果：遍历maxDp数组，取最大值即可。

代码实现（Java）

java

运行

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

三、两道题的核心对比与面试考点

表格

四、总结

1. 最长递增子序列：
   • 基础版 DP 是理解动态规划状态定义和转移的绝佳例子。
   • 优化版的贪心 + 二分，体现了如何用额外的空间和更高效的算法，突破 DP 的时间复杂度瓶颈。
2. 乘积最大子数组：
   • 核心是打破思维定势，不像 “最大子数组和” 只维护一个最大值，而是要同时维护最大和最小值，因为负数的存在会让最小值变成最大值。