Find Maximum Product Subarray In A Given Array In C

When working with arrays, finding a contiguous subarray that yields the maximum product presents a unique challenge, particularly due to the presence of negative numbers and zeros. Unlike maximum sum subarray problems, negative numbers can turn a very small product into a very large one when multiplied by another negative number. In this article, you will learn how to efficiently find the maximum product subarray within a given array of integers in C.

Problem Statement

Given an integer array nums, find a contiguous non-empty subarray that has the largest product, and return the product. A subarray is a contiguous part of an array.

For instance, consider the array [-2, 0, -1]. The maximum product subarray is 0, not -1 or -2, because a subarray must be contiguous. The problem requires handling positive numbers, negative numbers, and zeros, ensuring that the subarray is contiguous and non-empty.

Example

Let's take an array [2, 3, -2, 4]. Possible subarrays and their products:

• [2] -> 2
• [2, 3] -> 6
• [2, 3, -2] -> -12
• [2, 3, -2, 4] -> -48
• [3] -> 3
• [3, -2] -> -6
• [3, -2, 4] -> -24
• [-2] -> -2
• [-2, 4] -> -8
• [4] -> 4

 

The maximum product in this example is 6, from the subarray [2, 3].

Background & Knowledge Prerequisites

To understand the solutions presented, you should be familiar with:

• Basic C Programming: Variables, data types, loops (for loops), conditional statements (if-else).
• Arrays: Declaring and accessing elements in single-dimensional arrays.
• Functions: Defining and calling functions in C.

 

No specific libraries are required beyond the standard input/output library (stdio.h).

Use Cases or Case Studies

Finding the maximum product subarray can be useful in various scenarios:

• Financial Analysis: Identifying periods in stock market data where the compound growth rate (product of daily returns) was highest.
• Signal Processing: Detecting sections of a signal with the highest cumulative amplification.
• Bioinformatics: Analyzing sequences where certain segments show a strong multiplicative effect of properties.
• Image Processing: Optimizing filter application where pixel values multiply.
• Algorithm Optimization: As a sub-problem in more complex algorithms dealing with multiplicative properties.

 

Solution Approaches

We will explore two primary approaches: a straightforward brute-force method and a more efficient dynamic programming-inspired solution.

1. Brute Force Approach

The brute-force approach involves checking every possible contiguous subarray, calculating its product, and keeping track of the maximum product found.

• Summary: Iterate through all possible starting and ending points of subarrays, compute the product for each, and update the global maximum.

 

// Maximum Product Subarray (Brute Force)
#include <stdio.h>
#include <limits.h> // For INT_MIN

int maxProductBruteForce(int nums[], int n) {
    if (n == 0) {
        return 0; // Or handle as an error, depending on requirements
    }

    int max_product = INT_MIN; // Initialize with the smallest possible integer value

    // Step 1: Iterate through all possible starting points (i)
    for (int i = 0; i < n; i++) {
        int current_product = 1;
        // Step 2: Iterate through all possible ending points (j) starting from i
        for (int j = i; j < n; j++) {
            current_product *= nums[j]; // Step 3: Calculate product for subarray nums[i...j]
            if (current_product > max_product) {
                max_product = current_product; // Step 4: Update max_product if current_product is greater
            }
        }
    }
    return max_product;
}

int main() {
    int nums1[] = {2, 3, -2, 4};
    int n1 = sizeof(nums1) / sizeof(nums1[0]);
    printf("Array: [2, 3, -2, 4], Max Product: %d\\n", maxProductBruteForce(nums1, n1));

    int nums2[] = {-2, 0, -1};
    int n2 = sizeof(nums2) / sizeof(nums2[0]);
    printf("Array: [-2, 0, -1], Max Product: %d\\n", maxProductBruteForce(nums2, n2));

    int nums3[] = {-1, -2, -9, -6};
    int n3 = sizeof(nums3) / sizeof(nums3[0]);
    printf("Array: [-1, -2, -9, -6], Max Product: %d\\n", maxProductBruteForce(nums3, n3));

    int nums4[] = {6, -3, -10, 0, 2};
    int n4 = sizeof(nums4) / sizeof(nums4[0]);
    printf("Array: [6, -3, -10, 0, 2], Max Product: %d\\n", maxProductBruteForce(nums4, n4));

    return 0;
}

Run

• Sample Output:

Array: [2, 3, -2, 4], Max Product: 6
Array: [-2, 0, -1], Max Product: 0
Array: [-1, -2, -9, -6], Max Product: 108
Array: [6, -3, -10, 0, 2], Max Product: 180

 

• Stepwise Explanation:

1. Initialize maxproduct to INTMIN to correctly handle cases with negative numbers or single-element arrays.
2. Use an outer loop (i) to select every possible starting index of a subarray.
3. Use an inner loop (j) to select every possible ending index of a subarray, starting from i.
4. Inside the inner loop, currentproduct accumulates the product of elements from nums[i] to nums[j].
5. After each element nums[j] is multiplied, compare currentproduct with maxproduct and update maxproduct if currentproduct is greater.
6. After iterating through all subarrays, maxproduct holds the desired result.

2. Optimized Dynamic Programming Approach

The optimized approach tracks both the maximum and minimum products ending at the current position. This is crucial because a negative number multiplied by another negative number can yield a positive product, potentially the maximum.

• Summary: Iterate through the array, maintaining the maximum and minimum product subarrays ending at the current position. Update a global maximum product found so far.

 

// Maximum Product Subarray (Optimized DP)
#include <stdio.h>
#include <limits.h> // For INT_MIN
#include <stdlib.h> // For max/min functions

// Helper functions for max and min
int max(int a, int b) {
    return (a > b) ? a : b;
}

int min(int a, int b) {
    return (a < b) ? a : b;
}

int maxProductOptimized(int nums[], int n) {
    if (n == 0) {
        return 0; // Handle empty array case
    }

    int max_so_far = nums[0]; // Overall maximum product found
    int current_max = nums[0]; // Maximum product ending at the current position
    int current_min = nums[0]; // Minimum product ending at the current position

    // Step 1: Iterate through the array starting from the second element
    for (int i = 1; i < n; i++) {
        int temp_current_max = current_max; // Store current_max before it potentially changes

        // Step 2: Calculate current_max for nums[i]
        // It can be nums[i] itself, or current_max * nums[i], or current_min * nums[i] (if nums[i] is negative)
        current_max = max(nums[i], max(current_max * nums[i], current_min * nums[i]));

        // Step 3: Calculate current_min for nums[i]
        // It can be nums[i] itself, or temp_current_max * nums[i], or current_min * nums[i]
        current_min = min(nums[i], min(temp_current_max * nums[i], current_min * nums[i]));

        // Step 4: Update the overall maximum product
        max_so_far = max(max_so_far, current_max);
    }

    return max_so_far;
}

int main() {
    int nums1[] = {2, 3, -2, 4};
    int n1 = sizeof(nums1) / sizeof(nums1[0]);
    printf("Array: [2, 3, -2, 4], Max Product: %d\\n", maxProductOptimized(nums1, n1));

    int nums2[] = {-2, 0, -1};
    int n2 = sizeof(nums2) / sizeof(nums2[0]);
    printf("Array: [-2, 0, -1], Max Product: %d\\n", maxProductOptimized(nums2, n2));

    int nums3[] = {-1, -2, -9, -6};
    int n3 = sizeof(nums3) / sizeof(nums3[0]);
    printf("Array: [-1, -2, -9, -6], Max Product: %d\\n", maxProductOptimized(nums3, n3));

    int nums4[] = {6, -3, -10, 0, 2};
    int n4 = sizeof(nums4) / sizeof(nums4[0]);
    printf("Array: [6, -3, -10, 0, 2], Max Product: %d\\n", maxProductOptimized(nums4, n4));
    
    int nums5[] = {1};
    int n5 = sizeof(nums5) / sizeof(nums5[0]);
    printf("Array: [1], Max Product: %d\\n", maxProductOptimized(nums5, n5));

    int nums6[] = {0, 2};
    int n6 = sizeof(nums6) / sizeof(nums6[0]);
    printf("Array: [0, 2], Max Product: %d\\n", maxProductOptimized(nums6, n6));

    return 0;
}

Run

• Sample Output:

Array: [2, 3, -2, 4], Max Product: 6
Array: [-2, 0, -1], Max Product: 0
Array: [-1, -2, -9, -6], Max Product: 108
Array: [6, -3, -10, 0, 2], Max Product: 180
Array: [1], Max Product: 1
Array: [0, 2], Max Product: 2

 

• Stepwise Explanation:

1. Initialize maxsofar, currentmax, and currentmin with the first element of the array. maxsofar tracks the overall maximum product found. currentmax tracks the maximum product subarray ending at the current index, and currentmin tracks the minimum product subarray ending at the current index.
2. Iterate through the array starting from the second element (i = 1).
3. For each element nums[i]:
   • Store the current currentmax in a temporary variable (tempcurrentmax) because currentmax will be updated first, and currentmin calculation might still need the old currentmax.

• Calculate the new currentmax: It can be nums[i] itself, the product of currentmax (from previous step) and nums[i], or the product of currentmin (from previous step) and nums[i] (if nums[i] is negative, currentmin * nums[i] might become the new maximum).
• Calculate the new currentmin: Similarly, it can be nums[i] itself, the product of tempcurrentmax and nums[i], or the product of currentmin (from previous step) and nums[i].
• This update logic correctly handles positive, negative, and zero elements. If nums[i] is zero, both currentmax and currentmin will effectively reset to 0, reflecting that any subarray ending at 0 will have a product of 0.

1. Update maxsofar with the maximum between maxsofar and the current currentmax.
2. After the loop finishes, maxsofar will hold the maximum product of any contiguous subarray.

Conclusion

Finding the maximum product subarray requires careful consideration of negative numbers, which can unexpectedly turn small products into large ones. While a brute-force approach provides a correct solution, its quadratic time complexity makes it inefficient for large arrays. The optimized dynamic programming approach significantly improves performance by tracking both maximum and minimum products ending at each position, achieving a linear time complexity.

Summary

• The problem involves finding the contiguous subarray with the largest product.
• Negative numbers are crucial: two negatives multiply to a positive.
• Brute-Force Solution:
• Time Complexity: O(N^2).
• Iterates through all possible start and end indices.
• Calculates product for each subarray.
• Optimized (Dynamic Programming) Solution:
• Time Complexity: O(N).
• Maintains currentmax and currentmin products ending at the current index.
• currentmax is updated by considering nums[i], currentmax * nums[i], and currentmin * nums[i].
• currentmin is updated similarly.
• A global maxso_far tracks the overall maximum.
• Handles zeros and single-element arrays correctly.