Problem description:

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Solution:

Use a res variable to denote the maximum result to return. In addition, two variables imin and imax for to store current maximum value and current minimum value. Why do we need to store the minimum value? The smallest product, which is the largest in the negative sense could become the maximum when being multiplied by a negative number.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # Since the number could be negative, nums[-1] might be negative as well
        # Keep tracking the smallest product and largest product in array
        # If nums[i] is negative, we swap the (min_p, max_p) because smaller number*negative would be bigger than large number*negative
        # ex: 3*-1 > 10*-1
        
        min_p, max_p, res = nums[0], nums[0], nums[0]
        for i in range(1, len(nums)):
            if nums[i] < 0:
                min_p, max_p = max_p, min_p
            min_p = min(min_p*nums[i], nums[i]) # ex: min(3*-1, -1)
            max_p = max(max_p*nums[i], nums[i]) # ex: max(-2*5, 5)
            res = max(res, max_p)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        
    // store the result that is the max we have found so far
        int r = nums[0];

        // imax/imin stores the max/min product of
        // subarray that ends with the current number A[i]
        for (int i = 1, imax = r, imin = r; i < nums.size(); i++) {
            // multiplied by a negative makes big number smaller, small number bigger
            // so we redefine the extremums by swapping them
            if (nums[i] < 0)
                swap(imax, imin);

            // max/min product for the current number is either the current number itself
            // or the max/min by the previous number times the current one
            imax = max(nums[i], imax * nums[i]);
            imin = min(nums[i], imin * nums[i]);

            // the newly computed max value is a candidate for our global result
            r = max(r, imax);
        }
        return r;
    
    }
};

time complexity: $O(n)$
reference:
https://goo.gl/Eu7Vb4
https://goo.gl/fDPzc1