152. Maximum Product Subarray

Problem

Given an integer array nums, find a subarray that has the largest product, and return the product.

A subarray is a contiguous non-empty sequence of elements within an array.

The test cases are generated so that the answer will fit in a 32-bit integer.

https://leetcode.com/problems/maximum-product-subarray/

Example 1:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Constraints:

1 <= nums.length <= 2 * 10^4
-10 <= nums[i] <= 10
The product of any subarray of nums is guaranteed to fit in a 32-bit integer.

Test Cases

1 2	class Solution: def maxProduct(self, nums: List[int]) -> int:

solution_test.py

import pytest

from solution import Solution


@pytest.mark.parametrize('nums, expected', [
    ([2,3,-2,4], 6),
    ([-2,0,-1], 0),

    ([5], 5),
    ([0], 0),
    ([-5], -5),
    ([-5, -2], 10),
    ([-5, 2], 2),
    ([-5, 0], 0),
])
class Test:
    def test_solution(self, nums, expected):
        sol = Solution()
        assert sol.maxProduct(nums) == expected

Thoughts

对于非零整数，相乘的数字个数越多，乘积的绝对值也会越大，决定是极大还是极小的关键就是负数个数的奇偶性。所以只要负数个数是偶数，数字越多越好。

0 乘以任何数结果都是 0，所以要先把 0 排除。用 0 所在的位置把整个数组切割成若干个不含零的小段，求每个小段能得到的最大乘积即可。

一个不含 0 的数组，如果负数个数是偶数，那么全部相乘，乘积最大。

如果只有一个负数，负数左边部分的乘积，与其右边部分的乘积，取最大即可。

如果有超过一个的奇数个负数，易知以最两头的负数之一分割数组，有可能得到最大乘积，而不能用任何中间的负数分割。设 0 <= i < j < n 是最两头的负数的位置，最大乘积只可能出自 Π(nums[0:j]) 或 Π(nums[i+1:n])。

时间复杂度 O(n)。

Code

solution.py

from typing import List


def prod(*args):
    res = 1
    did = False
    for v in args:
        if v != 0:
            res *= v
            did = True

    return res if did else 0


class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if (n := len(nums)) == 1:
            return nums[0]

        # Once there are at least two numbers, the largest product must be >= 0.
        largest = 0

        # [prod(left subarray), first <0 number, prod(mid subarray), last <0 number, prod(right subarray)]
        parts = [0]
        for i in range(n + 1):
            if i >= n or (v := nums[i]) == 0: # End of a non-zero subarray.
                if len(parts) < 5: # Zero or one negative number.
                    largest = max(largest, *parts)
                elif parts[2] >= 0: # Negative numbers' count is even (prod(mid) >= 0).
                    largest = max(largest, prod(*parts))
                else: # Negative numbers' count is odd.
                    largest = max(largest, prod(*parts[:3]), prod(*parts[2:]))

                parts = [0]
            elif v > 0:
                parts[-1] = prod(parts[-1], v)
            else:
                if len(parts) < 5:
                    parts.extend((v, 0))
                else:
                    parts[2] = prod(*parts[2:])
                    parts[3] = v
                    parts[4] = 0

        return largest

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。