Back to DSA
Maximum Product Subarray
hardGiven an integer array, identify the contiguous subarray whose product of elements is the largest and return that product.
Examples
Example 1:
Input:
nums = [3,-1,4,-2]Output:
24Explanation: The entire array has product 3*(-1)*4*(-2) = 24.
Example 2:
Input:
nums = [-3,0,2,-5]Output:
2Explanation: The single element [2] gives the maximum product.
Hints
class Solution {
public int maxProduct(int[] nums) {
int maxProd = nums[0], minProd = nums[0], result = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] < 0) { int temp = maxProd; maxProd = minProd; minProd = temp; }
maxProd = Math.max(nums[i], maxProd * nums[i]);
minProd = Math.min(nums[i], minProd * nums[i]);
result = Math.max(result, maxProd);
}
return result;
}
}Time complexity
O(n)Space complexity
O(1)