🧠 DP 实战进阶：最长递增子序列、乘积最大子数组、分割等和子集（LeetCode 300 / 152 / 416）

在动态规划的学习路径中，这三道题常被视作进阶经典，它们分别对应不同的状态定义与优化思路：

• 📈 300. 最长递增子序列（LIS）：子序列类动态规划
• ✖️ 152. 乘积最大子数组：带正负号波动的区间 DP
• 🎯 416. 分割等和子集：0-1 背包问题的变种

📈 一、300. 最长递增子序列

📌 题目描述

给你一个整数数组 nums，返回其中最长严格递增子序列的长度。

💡 解题思路（一）：动态规划

状态定义：

• dp[i] 表示以 nums[i] 结尾的最长递增子序列长度。

状态转移方程：

for j := 0; j < i; j++ {
   
    if nums[i] > nums[j] {
   
        dp[i] = max(dp[i], dp[j] + 1)
    }
}

时间复杂度：O(n²)

✅ Go 实现

func lengthOfLIS(nums []int) int {
   
    n := len(nums)
    dp := make([]int, n)
    for i := range dp {
   
        dp[i] = 1
    }

    maxLen := 1
    for i := 1; i < n; i++ {
   
        for j := 0; j < i; j++ {
   
            if nums[i] > nums[j] {
   
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
        maxLen = max(maxLen, dp[i])
    }
    return maxLen
}

func max(a, b int) int {
   
    if a > b {
   
        return a
    }
    return b
}

💡 解法（二）：二分优化（贪心 + 二分）

维护一个数组 tails，tails[i] 表示长度为 i+1 的递增子序列中末尾最小的值。

时间复杂度：O(n log n)

✖️ 二、152. 乘积最大子数组

📌 题目描述

给你一个整数数组 nums，找出一个乘积最大的连续子数组，返回该乘积。

💡 解题思路

因为负负得正的存在，我们需要同时记录当前的最大值和最小值：

• dpMax[i]：以 i 结尾的最大乘积
• dpMin[i]：以 i 结尾的最小乘积

状态转移：

dpMax[i] = max(nums[i], nums[i]*dpMax[i-1], nums[i]*dpMin[i-1])
dpMin[i] = min(nums[i], nums[i]*dpMax[i-1], nums[i]*dpMin[i-1])

✅ Go 实现（空间优化）

func maxProduct(nums []int) int {
   
    maxVal, minVal := nums[0], nums[0]
    res := nums[0]

    for i := 1; i < len(nums); i++ {
   
        tempMax := maxVal
        maxVal = max(nums[i], max(nums[i]*maxVal, nums[i]*minVal))
        minVal = min(nums[i], min(nums[i]*tempMax, nums[i]*minVal))
        res = max(res, maxVal)
    }
    return res
}

🎯 三、416. 分割等和子集

📌 题目描述

给定一个只包含正整数的非空数组，判断能否将其分成两个子集，使得两个子集的和相等。

💡 解题思路

转换为 0-1 背包问题：

• 目标是找到一个子集，使其和为 sum/2；
• 状态定义：dp[j] 表示是否存在和为 j 的子集；
• 状态转移：

dp[j] = dp[j] || dp[j - num]

✅ Go 实现

func canPartition(nums []int) bool {
   
    total := 0
    for _, num := range nums {
   
        total += num
    }
    if total%2 != 0 {
   
        return false
    }
    target := total / 2
    dp := make([]bool, target+1)
    dp[0] = true

    for _, num := range nums {
   
        for j := target; j >= num; j-- {
   
            dp[j] = dp[j] || dp[j-num]
        }
    }
    return dp[target]
}

🔚 总结与对比

📘 写在最后

这三道题展示了动态规划在处理不同问题时的状态建模能力和转移逻辑多样性。可以举一反三，比如：

• LIS 拓展题：673. 最长递增子序列的个数
• 背包拓展题：494. 目标和
• 区间动态规划：42. 接雨水、91. 解码方法