Maximum Product Subarray In C,CPP,JAVA,PYTHON,C#,JS

Problem Statement: Maximum Product Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest product and return its product.

Example

Example 1:

Input:
nums = [2, 3, -2, 4]
Output:
6
Explanation: The subarray [2, 3] has the largest product 6.

Example 2:

Input:
nums = [-2, 0, -1]
Output:
0
Explanation: The subarray [0] has the largest product 0.

Approach and Algorithm

1. Dynamic Programming Approach:
   • The idea is to maintain two variables while iterating over the array:
     • maxProd: The maximum product subarray ending at the current index.
     • minProd: The minimum product subarray ending at the current index (this is important because a negative number could flip the sign and produce a larger positive product).
   • For each element, the maxProd and minProd are updated by considering:
     • The element itself.
     • The product of the element and the previous maxProd.
     • The product of the element and the previous minProd.
   • The result will be the maximum of maxProd seen so far.
2. Time Complexity:
   • O(n), where n is the length of the array, as we only make a single pass over the array.
3. Space Complexity:
   • O(1), because we are only using a constant amount of extra space.

Code in Multiple Languages

C

#include <stdio.h>
#include <limits.h>

int maxProduct(int* nums, int numsSize) {
    if (numsSize == 0) return 0;
    
    int maxProd = nums[0], minProd = nums[0], result = nums[0];
    
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] < 0) {
            // Swap maxProd and minProd when nums[i] is negative
            int temp = maxProd;
            maxProd = minProd;
            minProd = temp;
        }
        
        maxProd = (nums[i] > nums[i] * maxProd) ? nums[i] : nums[i] * maxProd;
        minProd = (nums[i] < nums[i] * minProd) ? nums[i] : nums[i] * minProd;
        
        result = (result > maxProd) ? result : maxProd;
    }
    
    return result;
}

int main() {
    int nums[] = {2, 3, -2, 4};
    int size = sizeof(nums) / sizeof(nums[0]);
    printf("Maximum product subarray: %d\n", maxProduct(nums, size));  // Output: 6
    return 0;
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxProduct(vector<int>& nums) {
    if (nums.empty()) return 0;
    
    int maxProd = nums[0], minProd = nums[0], result = nums[0];
    
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] < 0) {
            swap(maxProd, minProd);
        }
        
        maxProd = max(nums[i], nums[i] * maxProd);
        minProd = min(nums[i], nums[i] * minProd);
        
        result = max(result, maxProd);
    }
    
    return result;
}

int main() {
    vector<int> nums = {2, 3, -2, 4};
    cout << "Maximum product subarray: " << maxProduct(nums) << endl;  // Output: 6
    return 0;
}

Java

public class MaximumProductSubarray {
    public static int maxProduct(int[] nums) {
        if (nums.length == 0) return 0;
        
        int maxProd = nums[0], minProd = nums[0], result = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < 0) {
                int temp = maxProd;
                maxProd = minProd;
                minProd = temp;
            }
            
            maxProd = Math.max(nums[i], nums[i] * maxProd);
            minProd = Math.min(nums[i], nums[i] * minProd);
            
            result = Math.max(result, maxProd);
        }
        
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, -2, 4};
        System.out.println("Maximum product subarray: " + maxProduct(nums));  // Output: 6
    }
}

Python

def maxProduct(nums):
    if not nums:
        return 0
    
    maxProd = minProd = result = nums[0]
    
    for num in nums[1:]:
        if num < 0:
            maxProd, minProd = minProd, maxProd
        
        maxProd = max(num, num * maxProd)
        minProd = min(num, num * minProd)
        
        result = max(result, maxProd)
    
    return result

# Example
nums = [2, 3, -2, 4]
print("Maximum product subarray:", maxProduct(nums))  # Output: 6

C#

using System;

public class MaximumProductSubarray {
    public static int MaxProduct(int[] nums) {
        if (nums.Length == 0) return 0;

        int maxProd = nums[0], minProd = nums[0], result = nums[0];

        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] < 0) {
                int temp = maxProd;
                maxProd = minProd;
                minProd = temp;
            }

            maxProd = Math.Max(nums[i], nums[i] * maxProd);
            minProd = Math.Min(nums[i], nums[i] * minProd);

            result = Math.Max(result, maxProd);
        }

        return result;
    }

    public static void Main() {
        int[] nums = {2, 3, -2, 4};
        Console.WriteLine("Maximum product subarray: " + MaxProduct(nums));  // Output: 6
    }
}

JavaScript

function maxProduct(nums) {
    if (nums.length === 0) return 0;
    
    let maxProd = nums[0], minProd = nums[0], result = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] < 0) {
            [maxProd, minProd] = [minProd, maxProd];
        }
        
        maxProd = Math.max(nums[i], nums[i] * maxProd);
        minProd = Math.min(nums[i], nums[i] * minProd);
        
        result = Math.max(result, maxProd);
    }
    
    return result;
}

console.log("Maximum product subarray:", maxProduct([2, 3, -2, 4]));  // Output: 6

---

Summary

• Time Complexity: O(n), where n is the length of the input array nums. We traverse the array once.
• Space Complexity: O(1), because we only use a constant amount of extra space to store the intermediate results.
• Algorithm: Use dynamic programming to maintain both the maximum and minimum products up to each index. When encountering negative numbers, we swap the maximum and minimum products. The result will be the maximum product encountered during the traversal of the array.