Maximum Product Subarray

Posted on | Edited on | In | | Views:

152. Maximum Product Subarray

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

给一个数组， 求他的子序列中乘积最大的值

Example1:

input: [2, 3, -2, 4]
output: 6 -> [2, 3]

Example2:

input: [-2, 0, -1]
output: [0]

思路

从前往后扫这个数组, 记录下 max_product和min_product.
因为对于他的子序列来说, 最大的积有几种可能.

  1. 之前最大的乘积乘以一个正数
  2. 之前最小的乘积乘以一个负数
  3. 当前的数字就是最大的

最小的积也是一样的道理.

Code

1
2
3
4
5
6
7
8
9
10
11
def max_product(nums):
    if not nums:
        return 0
    res = nums[0]
    max_p = min_p = num[0]
    for i in range(1, len(nums)):
        tmp = min_p
        min_p = min(nums[i], min_p * nums[i], max_p * nums[i])
        max_p = max(nums[i], tmp * nums[i], max_p * nums[i])
        res = max(res, max_p)
    return res

Example1:

[2, 3, -2, 4]
i = 1
    min_p = min(3, 2 * 3, 2 * 3) = 3
    max_p = max(3, 2, * 3, 2 * 3) = 6
    res = 6
i = 2
    min_p = min(-2, 6 * -2, 3 * -2) = -12
    max_p = max(-2, 6 * -2, 3 * -2) = -2
    res = 6
...

Example2:

[-2, 0, -1]
i = 1
    min_p = min(0, -2 * 0, -2 * 0) = 0
    max_p = max(0, -2 * 0, -2 * 0) = 0
    res = 0
i = 2
    min_p = min(0, -1 * 0, -1 * 0) = 0
    max_p = max(0, -1 * 0, -1 * 0) = 0
    res = 0

时间复杂度

$O(n)$