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.
1#include <stdio.h>
2
3int maxProduct(int* nums, int numsSize) {
4 int maxProduct = nums[0];
5 int currMax = nums[0];
6 int currMin = nums[0];
7 for(int i = 1; i < numsSize; i++) {
8 if (nums[i] < 0) {
9 int temp = currMax;
10 currMax = currMin;
11 currMin = temp;
12 }
13 currMax = nums[i] > nums[i] * currMax ? nums[i] : nums[i] * currMax;
14 currMin = nums[i] < nums[i] * currMin ? nums[i] : nums[i] * currMin;
15 maxProduct = currMax > maxProduct ? currMax : maxProduct;
16 }
17 return maxProduct;
18}
19
20int main() {
21 int nums[] = {2, 3, -2, 4};
22 int size = sizeof(nums) / sizeof(nums[0]);
23 printf("%d\n", maxProduct(nums, size));
24 return 0;
25}The C solution initializes variables for the maximum and minimum products at the starting element of the array. We then iterate through the array, swapping the current max and min products when encountering a negative number, thereby adjusting the maximum product accordingly.
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.