Ricky.L的随笔
0%

LeetCode.152.乘积最大子数组（中等）

发表于 更新于 分类于 Disqus：

题目

LeetCode.152.乘积最大子数组（中等）

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

题解

最值问题考虑用动态规划。

为了方便描述，设maxProduct[i]为以nums[i]结尾的子数组的最大乘积。

求maxProduct[i]，nums[i]肯定少不了，因为子数组最少需要一个元素。

求maxProduct[i]有哪些可能的组合情况？

  1. nums[i]自己单独成为一个子数组。
    比如前面子数组乘积是0，nums[i]为正数，就没必要跟前面相乘了。但是nums[i]可能会比前面子数组乘积要小，所以要看看其他情况。
  2. nums[i]跟前面的子数组的乘积相乘。
    接下来就是看怎么跟nums[i]相乘可以得到尽可能大的乘积。

有哪些乘法情况可以使乘积变大？

  1. 正数 * 正数
  2. 负数 * 负数

也就是说求maxProduct[i]要记录nums[i]前面的子数组的最大乘积和最小乘积。

穷举求maxProduct[i]要考虑的情况

  1. nums[i]单独成为一个子数组
  2. nums[i]乘以i前面的子数组最大的乘积
  3. nums[i]乘以i前面的子数组最小的乘积

求maxProduct[i]就是取三者最大值

状态转移方程

maxProduct[i] = max(nums[i], nums[i] * maxProduct[i - 1], nums[i] * minProduct[i - 1])

怎么求以nums[i]结尾的连续子数组的最小乘积？

跟考虑求最大乘积思路一样。
使乘积变得更小的方式就是正数和负数相乘。
nums[i]可能为正也可能为负，所以minProduct[i]的求解也是有maxProduct[i]的那三种情况，只不过是求最小值。

边界情况

maxProduct[0]就是nums[i]本身，因为以nums[0]为结尾的子数组就是nums[0]本身构成的一个元素的子数组。
同理，minProduct[0]也是nums[i]。

递推要从i = 1开始。

空间优化

当前状态只跟上一步状态有关，所以不需要用数组存储所有状态，用几个变量记录上一步状态即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    fun maxProduct(nums: IntArray): Int {
        val n = nums.size
        if (n == 0) return 0
        if (n == 1) return nums[0]
        var minProduct = nums[0]
        var maxProduct = nums[0]
        var result = maxProduct
        for (i in 1 until n) {
            val num = nums[i]
            val newMaxProduct = maxOf(num, num * maxProduct, num * minProduct)
            minProduct = minOf(num, num * maxProduct, num * minProduct)
            maxProduct = newMaxProduct
            result = maxOf(result, maxProduct)
        }
        return result
    }
}