LeetCode 152 乘积最大子序列 [Swift]

2019-12-10

题目

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例1:

输入: [2,3,-2,4]

输出: 6

解释: 子数组 [2,3] 有最大乘积 6。

示例2:

输入: [-2,0,-1]

输出: 0

解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

思路

初步对问题进行分析，本题的目标是找到乘积最大的子序列，其中避免不了有一些重复的乘运算，我们能否将这些重复的耗时逻辑尽可能减少。为了达到这个目标，如果对 动态规划 的特点（利用历史记录，来避免重复计算）了解的话，我们可以确定算法的初步方向。

针对动态规划问题，一般的求解步骤是：

确定数据结构
确定连续数据结构的关系式
初始值赋值，然后遍历计算

具体针对本题的场景：

我们先定义一个数组 dpMax，用 dpMax[i] 表示以第 i 个元素的结尾的子数组，乘积最大的值，也就是这个数组必须包含第 i 个元素。

那么 dpMax[i] 的话有几种取值：

当 nums[i] >= 0 并且 dpMax[i-1] > 0，dpMax[i] = dpMax[i-1] * nums[i]
当 nums[i] >= 0 并且 dpMax[i-1] < 0，此时如果和前边的数累乘的话，会变成负数，所以dpMax[i] = nums[i]

当 nums[i] < 0，此时如果前边累乘结果是一个很大的负数，和当前负数累乘的话就会变成一个更大的数。所以我们还需要一个数组 dpMin 来记录以第 i 个元素的结尾的子数组，乘积最小的值：

当 nums[i] < 0 并且 dpMin[i-1] < 0，dpMax[i] = dpMin[i-1] * nums[i]
当 nums[i] < 0 并且 dpMin[i-1] >= 0，dpMax[i] = nums[i]

当然，上边引入了 dpMin 数组，怎么求 dpMin 其实和上边求 dpMax 的过程其实是一样的。

按上边的分析，我们就需要加很多的 if else来判断不同的情况，这里可以用个技巧。

我们注意到上边dpMax[i] 的取值无非就是三种，dpMax[i-1] * nums[i]、dpMin[i-1] * nums[i] 以及 nums[i]。

所以我们更新的时候，无需去区分当前是哪种情况，只需要从三个取值中选一个最大的即可，代码实现如下：

class Solution {
    func maxProduct(_ nums: [Int]) -> Int {
        let size = nums.count
        if size == 0 {
            return 0
        }
        var dpMax = Array.init(repeating: 0, count: size)
        var dpMin = Array.init(repeating: 0, count: size)
        dpMin[0] = nums[0]
        dpMax[0] = nums[0]
        var maxValue = nums[0]
        for i in 1..<size {
            dpMax[i] = max(dpMin[i - 1] * nums[i], max(dpMax[i - 1] * nums[i], nums[i]))
            dpMin[i] = min(dpMin[i - 1] * nums[i], min(dpMax[i - 1] * nums[i], nums[i]))
            maxValue = max(maxValue, dpMax[i])
        }
        return maxValue
    }
}

本题完成后，如果感觉对 动态规划 还是有点懵，推荐阅读下面这篇关于动态规划类算法的套路总结，然后再刷几道动态规划类型的题目进行实践，相信你会有更深的感受！

LeetCode 152 乘积最大子序列 [Swift]

题目

思路

技术

算法

项目