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

The problem can be solved using dynamic programming (DP) with two DP arrays:

f[i] represents the largest sub-array product within the range of sub-array [0, i] that must contain the number nums[i],
g[i] represents the smallest sub-array product within the range of sub-array [0, i] that must contain the number nums[i].

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:

f[i-1]*nums[i],
g[i-1]*nums[i], and
nums[i].

Therefore, we can use the maximum of the three to update f[i] and the minimum to update g[i]. Then, use f[i] to update the result.

It’s important to note that since the final result may not include the number nums[n-1], f[n-1] is not necessarily the final solution. The constantly updated result should be returned instead.

Code

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);
	    }
	}
}

############

class Solution {
    public int maxProduct(int[] nums) {
        int maxf = nums[0], minf = nums[0], res = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            int m = maxf, n = minf;
            maxf = Math.max(nums[i], Math.max(m * nums[i], n * nums[i]));
            minf = Math.min(nums[i], Math.min(m * nums[i], n * nums[i]));
            res = Math.max(res, maxf);
        }
        return res;
    }
}

// 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:
    def maxProduct(self, nums: List[int]) -> int:
        maxf = minf = res = nums[0]
        for num in nums[1:]:
            m, n = maxf, minf
            maxf = max(num, m * num, n * num)
            minf = min(num, m * num, n * num)
            res = max(res, maxf)
        return res

############

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

func maxProduct(nums []int) int {
	maxf, minf, res := nums[0], nums[0], nums[0]
	for i := 1; i < len(nums); i++ {
		m, n := maxf, minf
		maxf = max(nums[i], max(nums[i]*m, nums[i]*n))
		minf = min(nums[i], min(nums[i]*m, nums[i]*n))
		res = max(res, maxf)
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

function maxProduct(nums: number[]): number {
    let n = nums.length;
    let preMax = nums[0],
        preMin = nums[0],
        ans = nums[0];
    for (let i = 1; i < n; ++i) {
        let cur = nums[i];
        let x = preMax,
            y = preMin;
        preMax = Math.max(x * cur, y * cur, cur);
        preMin = Math.min(x * cur, y * cur, cur);
        ans = Math.max(preMax, ans);
    }
    return ans;
}

public class Solution {
    public int MaxProduct(int[] nums) {
        int maxf = nums[0], minf = nums[0], res = nums[0];
        for (int i = 1; i < nums.Length; ++i)
        {
            int m = maxf, n = minf;
            maxf = Math.Max(nums[i], Math.Max(nums[i] * m, nums[i] * n));
            minf = Math.Min(nums[i], Math.Min(nums[i] * m, nums[i] * n));
            res = Math.Max(res, maxf);
        }
        return res;
    }
}

impl Solution {
    pub fn max_product(nums: Vec<i32>) -> i32 {
        let mut min = nums[0];
        let mut max = nums[0];
        let mut res = nums[0];
        for &num in nums.iter().skip(1) {
            let (pre_min, pre_max) = (min, max);
            min = num.min(num * pre_min).min(num * pre_max);
            max = num.max(num * pre_min).max(num * pre_max);
            res = res.max(max);
        }
        res
    }
}

152 - Maximum Product Subarray

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions