This approach maintains two variables for each element in the array: the maximum product up to that element and the minimum product up to that element. We update these variables as we iterate through the array. This accommodates both the product of consecutive elements and the inversion effect caused by negative numbers.
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1), as we are using only a constant amount of extra space.
1public class MaxProductSubarray {
2 public static int maxProduct(int[] nums) {
3 int maxProduct = nums[0];
4 int currMax = nums[0];
5 int currMin = nums[0];
6 for (int i = 1; i < nums.length; i++) {
7 if (nums[i] < 0) {
8 int temp = currMax;
9 currMax = currMin;
10 currMin = temp;
11 }
12 currMax = Math.max(nums[i], nums[i] * currMax);
13 currMin = Math.min(nums[i], nums[i] * currMin);
14 maxProduct = Math.max(maxProduct, currMax);
15 }
16 return maxProduct;
17 }
18 public static void main(String[] args) {
19 int[] nums = {2, 3, -2, 4};
20 System.out.println(maxProduct(nums));
21 }
22}The Java implementation is close to that of C++, but using Java's Math manipulation functions to handle the calculations for current minimum and maximum products.
In this approach, we calculate the prefix product and suffix product for each element of the array, capturing the highest product subarray that may begin or end with an array boundary. We track the maximum of the prefix or suffix products.
Time Complexity: O(n)
Space Complexity: O(1)
1def maxProduct(nums):
2 n = len(nums)
3 maxProduct = nums[0]
4 prefixProduct = 1
5 suffixProduct = 1
6 for i in range(n):
7 prefixProduct = 1 if prefixProduct == 0 else prefixProduct * nums[i]
8 suffixProduct = 1 if suffixProduct == 0 else suffixProduct * nums[n - 1 - i]
9 maxProduct = max(maxProduct, prefixProduct, suffixProduct)
10 return maxProduct
11
12print(maxProduct([2, 3, -2, 4]))Python calculates prefix and suffix products within a single traversal over the array with tuple unpacking for swaps. Updates to maxProduct are done by comparing the accumulated products.