LeetCode 152. Maximum Product Subarray

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

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

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.

The solution can be done in O(n) runtime.

The problem is easy when all the input are postive. But problem comes when there are negative numbers in the input.

Funny thing about negative number. When multiplied with positive number, it can transform riches to rags and rags to riches.

Solution:

• Compute maximum iMaxand minimumiMinat each index i
• At each iteration, we evaluate iMax & iMinbased on previous values of iMax & iMinand the sign +/-of the current number.

if current number is positive:
    iMax = currentNumber * previous iMax
if current number is negative:
    iMax = currentNumber * previous iMin

This evaluation could be hard to see in the code. But it is acomplished by 
using the swap function.

• At each iteration, theiMaxshould be either the current number or the current number times max/min of previous index.
• Then finally, we update our result.

Python Code Version 1:

def maxSubArray(nums):
    result = nums[0]
    iMax, iMin = 1, 1
    
    for i in nums:
        if i < 0:
            iMax, iMin = iMin, iMax
        
        iMax = max(i, i*iMax)
        iMin = min(i, i*iMin)
        
        result = max(result, iMax)
        
    return result

Python Code Version 2:

def maxSubArray(nums):
    result = max(nums)
    iMax, iMin = 1, 1

    for n in nums:
        temp = iMax * n
        
        iMax = max(n, temp, n * iMin)
        iMin = min(n, temp, n * iMin)
        
        result = max(result, iMax)
     
    return result