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)
1#include <stdio.h>
2
3int maxProduct(int* nums, int numsSize) {
4 int maxProduct = nums[0];
5 int prefixProduct = 1;
6 int suffixProduct = 1;
7 for (int i = 0; i < numsSize; i++) {
8 prefixProduct = prefixProduct == 0 ? nums[i] : prefixProduct * nums[i];
9 suffixProduct = suffixProduct == 0 ? nums[numsSize - 1 - i] : suffixProduct * nums[numsSize - 1 - i];
10 maxProduct = prefixProduct > maxProduct ? prefixProduct : maxProduct;
11 maxProduct = suffixProduct > maxProduct ? suffixProduct : maxProduct;
12 }
13 return maxProduct;
14}
15
16int main() {
17 int nums[] = {2, 3, -2, 4};
18 int size = sizeof(nums) / sizeof(nums[0]);
19 printf("%d\n", maxProduct(nums, size));
20 return 0;
21}The C implementation iterates over the nums array, simultaneously updating prefix and suffix products. These products are reset to nums[i] or nums[numsSize-1-i] respectively if their accumulated product becomes zero.