Maximum Product Subarray

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

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)$