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.
1def maxProduct(nums):
2 maxProduct = nums[0]
3 currMax = nums[0]
4 currMin = nums[0]
5 for i in range(1, len(nums)):
6 if nums[i] < 0:
7 currMax, currMin = currMin, currMax
8 currMax = max(nums[i], nums[i] * currMax)
9 currMin = min(nums[i], nums[i] * currMin)
10 maxProduct = max(maxProduct, currMax)
11 return maxProduct
12
13print(maxProduct([2, 3, -2, 4]))Python's tuple unpacking makes swapping currMax and currMin straightforward when encountering negative numbers. The solution details remain the same.
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)
1using System;
2
3public class MaxProductSubarray {
4 public static int MaxProduct(int[] nums) {
5 int maxProduct = nums[0];
6 int prefixProduct = 1;
7 int suffixProduct = 1;
8 for (int i = 0; i < nums.Length; i++) {
9 prefixProduct = prefixProduct == 0 ? nums[i] : prefixProduct * nums[i];
10 suffixProduct = suffixProduct == 0 ? nums[nums.Length - 1 - i] : suffixProduct * nums[nums.Length - 1 - i];
11 maxProduct = Math.Max(maxProduct, Math.Max(prefixProduct, suffixProduct));
12 }
13 return maxProduct;
14 }
15 public static void Main() {
16 int[] nums = {2, 3, -2, 4};
17 Console.WriteLine(MaxProduct(nums));
18 }
19}In C#, simultaneous loop iterations adjusting prefixProduct and suffixProduct coupled with use of Math.Max provide efficient tracking of the greatest product subarray.