Given an integer array nums, find a contiguous non-empty subarray whose product is as large as possible and return that product. The answer is guaranteed to fit in a 32-bit integer.
[2,3] has product 6.[-2,-1] is not contiguous, so the best is the single element 0.- 1 <= nums.length <= 2 * 10^4
- -10 <= nums[i] <= 10
- Every prefix or suffix product fits in a 32-bit integer
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force tries every subarray and multiplies, which is O(n^2). For sums, Kadane keeps only the best sum ending at the current index. Products are trickier because a negative number flips the sign: the smallest (most negative) product so far turns into the largest after multiplying by a negative. So we keep two values for subarrays ending at i: hi (largest product) and lo (smallest product). The new hi is the largest of x, hi * x and lo * x, and the new lo is the smallest of the same three. A zero simply resets both to 0, and starting fresh at x handles it.
Algorithm
- Set
hi = lo = best = nums[0]. - For every next value
x, computea = hi * xandb = lo * x. - Update
hi = max(x, a, b)andlo = min(x, a, b)using the old values. - Update
best = max(best, hi). - Return
best.
O(n)Space: O(1)hi and lo before overwriting either one. Updating hi first and then using it for lo is the most common bug.class Solution: def maxProduct(self, nums: List[int]) -> int: hi = lo = best = nums[0] for x in nums[1:]: a, b = hi * x, lo * x # use the old hi and lo hi = max(x, a, b) lo = min(x, a, b) best = max(best, hi) return best