Welcome to Subscribe On Youtube

Question

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

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.

 

Constraints:

  • 1 <= nums.length <= 2 * 104
  • -10 <= nums[i] <= 10
  • The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

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
        }
    }
    
    
  • /**
     * @param {number[]} nums
     * @return {number}
     */
    var maxProduct = function (nums) {
        let [f, g, ans] = [nums[0], nums[0], nums[0]];
        for (let i = 1; i < nums.length; ++i) {
            const [ff, gg] = [f, g];
            f = Math.max(nums[i], ff * nums[i], gg * nums[i]);
            g = Math.min(nums[i], ff * nums[i], gg * nums[i]);
            ans = Math.max(ans, f);
        }
        return ans;
    };
    
    

All Problems

All Solutions