LeetCode 152 乘积最大子数组

本题与和最大的子数组相似，但是略有不同，其中差异值得反复研究。

题目描述

原题链接如下： LeetCode 152 乘积最大子数组

题目大意

找到乘积最大的连续子数组，并且输出其乘积。

输入与输出

数组输入内容可以为任意整数，示例输入为：

1
2
3
4
5

Input 1:
[2,3,-2,4]

Input 2:
[-2,0,-1]

子数组最短长度为 1，对应输出为：

1
2
3
4
5

Output 1:
6

Output 2:
0

解题思路

解法一：贪心

首先，要对子数组的元素符号分情况讨论：

• 包含 0 时，结果一定为 0
• 只包含正整数时，元素越多结果就越不可能减少
• 包含负整数时：
  • 有偶数个负数时，和只包含正整数的情况相同
  • 有奇数个负数时，原数组分为两部分：一部分只有 1 个负数，一部分有偶数个负数

是否包含 0 的情况容易处理，可以认为 0 把原数组分为多个碎片数组，每个碎片内部不包含 0，最后对比所有碎片数组的子数组最大乘积和 0 的大小关系即可。这样，就只需要处理不含 0 的数组中的负数个数问题。不难看出，偶数个负数的情况无需特殊处理，而奇数个负数时，要保证乘积最大则必定只会单独分出最左或者最右的负数不在子数组中。所以，只需要从左往右累乘元素，再从右往左累乘，比较两个乘积大小即可得到最大乘积。而且，偶数个负数和只包含正数时，两个乘积相等，也可以同时处理。 最后，左右两次累乘的解法也无需特意划分碎片数组，只要在累乘时遇到 0 就重新开始累乘即可，就相当于把划分操作包含在了累乘操作中。

解法二：动态规划

本题动态规划的状态容易定义，显然可以假设 dp(i) 为前 i + 1 个元素的子数组内最大乘积。但是，状态转移方程的推导则要十分注意：负数元素会改变乘积的符号，所以第 i 个元素为负数时，dp(i - 1) 和它相乘会得出最小乘积。所以，实际上我们还要定义一个状态以保存最小乘积，在元素为负数时和它相乘，而非负数时则和最大乘积相乘。最后的状态转移方程如下：

$$ \begin{aligned} dp_{max}(i) &= \begin{cases} \max {\lbrace dp_{min}(i - 1) \times nums[i], nums[i] \rbrace}, & nums[i] < 0 \\ \max {\lbrace dp_{max}(i - 1) \times nums[i], nums[i] \rbrace}, & nums[i] \geqslant 0 \end{cases} \\ dp_{min}(i) &= \begin{cases} \min {\lbrace dp_{max}(i - 1) \times nums[i], nums[i] \rbrace}, & nums[i] < 0 \\ \min {\lbrace dp_{min}(i - 1) \times nums[i], nums[i] \rbrace}, & nums[i] \geqslant 0 \end{cases} \end{aligned} $$

所以，我们实际上只要在第 i 个元素为负数时交换 $dp_{min}(i - 1)$ 和 $dp_{max}(i - 1)$ 的值即可。另外，因为第 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 {
        var re = nums[0]
        var product = 1
        val findMaxProduct: (IntProgression) -> Unit = {
            for (i in it) {
                product *= nums[i]
                re = maxOf(re, product)
                if (product == 0) product = 1
            }
        }

        findMaxProduct(nums.indices)
        product = 1
        findMaxProduct(nums.indices.reversed())
        return re
    }
}

解法二：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun maxProduct(nums: IntArray): Int {
        var preMax = nums[0]
        var preMin = nums[0]
        var re = preMax
        for (i in 1..nums.lastIndex) {
            val tmpMax = if (nums[i] < 0) preMin else preMax
            val tmpMin = if (nums[i] < 0) preMax else preMin
            preMax = maxOf(tmpMax * nums[i], nums[i])
            preMin = minOf(tmpMin * nums[i], nums[i])
            re = maxOf(preMax, re)
        }
        return re
    }
}