Question

Formatted question description: https://leetcode.ca/all/152.html

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

Example 1:

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

Example 2:

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


@tag-array

Algorithm

Do it with DP, and use two dp arrays,

  • Where f[i] represents the largest sub-array product within the range of sub-array [0, i] and must contain nums[i] numbers,
  • g[i] represents the smallest sub-array product within the range of sub-array [0, i] and must contain nums[i] numbers, During initialization, both f[0] and g[0] are initialized to nums[0], and the rest are initialized to 0.

Starting from the second number of the array, the maximum and minimum values at this time will only be generated between these three numbers, that is

  • f[i-1]*nums[i],
  • g[i-1]*nums[i],
  • And nums[i].

So use the maximum of the three to update f[i], use the minimum to update g[i], and then use f[i] to update the result.

Since the final result may not include the number nums[n-1], f[n-1] is not necessarily the final solution, and the constantly updated result is to be retuened.

Code

Java

  • 
    public class Maximum_Product_Subarray {
    
    	public class Solution {
    
    	    public int maxProduct(int[] A) {
    
    	        if(A==null || A.length==0)
    	            return 0;
    
    	        if(A.length == 1)
    	            return A[0];
    
    
    	        int max= A[0];
    	        int min = A[0];
    	        int finalmax = A[0];
    
    	        // just go through and multiply one by one till the end
    	        // mark max and min
    	        for (int i = 1; i < A.length; i++) {
    
    	            // max possible 1 2 3
    	            int maxp1 = A[i]; // if previous is 0, this one is positive
    	            int maxp2 = max * A[i];
    	            int maxp3 = min * A[i];
    
    	            int maxNotUpdated = max;
    	            max = findMax(maxp1, maxp2, maxp3);
    
    	            // min possible 1 2 3
    	            int minp1 = A[i]; // if previous is 0, this one is neg
    	            int minp2 = maxNotUpdated * A[i];
    	            int minp3 = min * A[i];
    
    	            min = findMin(minp1, minp2, minp3);
    
    	            if (max > finalmax) {
    	                finalmax = max;
    	            }
    
    	        }
    
    	        return finalmax;
    	    }
    
    	    public int findMax (int a, int b, int c) {
    
    	        return Math.max( Math.max(a,b), c);
    	    }
    
    	    public int findMin (int a, int b, int c) {
    
    	        return Math.min( Math.min(a,b), c);
    	    }
    	}
    }
    
  • // OJ: https://leetcode.com/problems/maximum-product-subarray/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        int maxProduct(vector<int>& A) {
            int ans = A[0], N = A.size(), j = 0;
            while (j < N) {
                int i = j, prod = 1;
                while (j < N && A[j] != 0) {
                    prod *= A[j++];
                    ans = max(ans, prod);
                }
                if (j < N) ans = max(ans, 0);
                while (i < N && prod < 0) {
                    prod /= A[i++];
                    if (i != j) ans = max(ans, prod);
                }
                while (j < N && A[j] == 0) ++j;
            }
            return ans;
        }
    };
    
  • class Solution(object):
      def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        maxDP = [0 for _ in range(0, len(nums))]
        minDP = [0 for _ in range(0, len(nums))]
        maxDP[0] = nums[0]
        minDP[0] = nums[0]
        ans = nums[0]
        for i in range(1, len(nums)):
          maxDP[i] = max(minDP[i - 1] * nums[i], nums[i], maxDP[i - 1] * nums[i])
          minDP[i] = min(minDP[i - 1] * nums[i], maxDP[i - 1] * nums[i], nums[i])
          ans = max(ans, maxDP[i])
        return ans
    
    

All Problems

All Solutions