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.
1function maxProduct(nums) {
2 let maxProduct = nums[0];
3 let currMax = nums[0];
4 let currMin = nums[0];
5 for (let i = 1; i < nums.length; i++) {
6 if (nums[i] < 0) {
7 let temp = currMax;
8 currMax = currMin;
9 currMin = temp;
10 }
11 currMax = Math.max(nums[i], nums[i] * currMax);
12 currMin = Math.min(nums[i], nums[i] * currMin);
13 maxProduct = Math.max(maxProduct, currMax);
14 }
15 return maxProduct;
16}
17
18console.log(maxProduct([2, 3, -2, 4]));JavaScript code responds similarly to other languages, with math functions to evaluate max and min products, facilitated by its in-built Math object.
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)
1public class MaxProductSubarray {
2 public static int maxProduct(int[] nums) {
3 int maxProduct = nums[0];
4 int prefixProduct = 1;
5 int suffixProduct = 1;
6 int n = nums.length;
7 for (int i = 0; i < n; i++) {
8 prefixProduct = prefixProduct == 0 ? nums[i] : prefixProduct * nums[i];
9 suffixProduct = suffixProduct == 0 ? nums[n - 1 - i] : suffixProduct * nums[n - 1 - i];
10 maxProduct = Math.max(maxProduct, Math.max(prefixProduct, suffixProduct));
11 }
12 return maxProduct;
13 }
14 public static void main(String[] args) {
15 int[] nums = {2, 3, -2, 4};
16 System.out.println(maxProduct(nums));
17 }
18}This Java solution achieves the maximum product by iterating over the array once, both forward and backward, managing prefix and suffix calculations simultaneously, and updating the max product accordingly.