Maximum product subarray
Medium
Given an integer array nums, find a subarray that has the largest product, and return the product. A subarray of an array is a contiguous sequence of elements within that array.
Example
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example
Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Approach
- Initialize variables
maxEndingHere
,minEndingHere
, andmaxProductSoFar
. - Iterate through the array from left to right, calculating
maxEndingHere
andminEndingHere
for each element. - Update
maxProductSoFar
by taking the maximum of the currentmaxProductSoFar
andmaxEndingHere
. - Continue the loop until all elements are processed.
- After the loop,
maxProductSoFar
will contain the maximum product of a subarray in the integer array.
Complexity
- Time Complexity: O(n), where 'n' is the length of the input array.
- Space Complexity: O(1), because the code uses a fixed number of variables.
Code
## Java Code
public class MaximumProductSubarray {
public int maxProduct(int[] nums) {
int n = nums.length;
if (n == 0)
return 0;
int maxEndingHere = nums[0];
int minEndingHere = nums[0];
int maxProductSoFar = nums[0];
for (int i = 1; i < n; i++) {
int tempMax = maxEndingHere;
maxEndingHere = Math.max(nums[i], Math.max(nums[i] * maxEndingHere, nums[i] * minEndingHere));
minEndingHere = Math.min(nums[i], Math.min(nums[i] * tempMax, nums[i] * minEndingHere));
maxProductSoFar = Math.max(maxProductSoFar, maxEndingHere);
}
return maxProductSoFar;
}
public static void main(String[] args) {
MaximumProductSubarray solution = new MaximumProductSubarray();
int[] nums = { 2, 3, -2, 4 };
int result = solution.maxProduct(nums);
System.out.println("Maximum subarray product: " + result);
}
}
Output
Maximum subarray product: 6
Thanks for feedback.