题目描述

[EN | CN]

给你一个整数数组 nums,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字)。

示例 1:

1
2
3
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

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

解法 1:动规

思路很简单,就是遍历一遍。但是这里要注意到数组里面可能存在负数,要稍微变动一下。

假如数组中只存在正数,那么我们保存一个 global_maxlocal_max,其中当遍历到第 i 个元素的时候,我们更新此时的 local_max,可能有两种情况:

  1. 上一个元素的 local_max 与当前元素的乘积;
  2. 丢弃之前的连续子数组,从当前元素重新开始。

我们对这两种情况取 max 即可。

而如果数组中可能存在负数,那么我们必须考虑「负负得正可能获得新的最大值」的情况,因此我们 local_max_pos 来保存绝对值最大的正数,用 local_max_neg 来保存绝对值最大的负数。当遍历到第 i 个元素的时候,此时的 local_max_pos(或 local_max_neg)可能有三种情况:

  1. 上一个元素的 local_max_pos(或 local_max_neg)与当前元素的乘积;
  2. 上一个元素的 local_max_neg(或 local_max_neg)与当前元素的乘积;
  3. 丢弃之前的连续子数组,从当前元素重新开始。

对于 local_max_pos,我们取 max;对于 local_max_neg,我们取 min

假设数组长度为 $n$,那么

  • 时间复杂度为 $O(n)$,遍历一遍;
  • 空间复杂度为 $O(1)$,不用额外空间。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        global_max = nums[0]
        local_max_pos = nums[0]
        local_max_neg = nums[0]

        for num in nums[1:]:
            local_max_pos, local_max_neg = (
                max(local_max_pos * num, local_max_neg * num, num),
                min(local_max_pos * num, local_max_neg * num, num)
            )
            global_max = max(global_max, local_max_pos)
        return global_max
  • 执行用时:44 ms,在所有 Python3 提交中击败了 94.25% 的用户。
  • 内存消耗:13.7 MB,在所有 Python3 提交中击败了 25.00% 的用户。