Maximum Product Subarray in C - Coding

In this article, we will learn how to find the product of the maximum product subarray for a given array that contains both positive and negative integers,

Example:

Input: 
arr[] = [2, 3, -2, 4]

Output: 
6

Explanation: [2, 3] has the largest product 6.

Table of Content

Method 1: Traversing Over Every Subarray
Method 2: Using Kadane’s Algorithm
Method 3: Using Traversal from Start and End of an Array

Solving the Maximum Product Subarray problem involves determining the subarray with the maximum product. There are several methods to achieve this in C.

Method 1: Traversing Over Every Subarray

In this method, we traverse over every contiguous subarray, calculate the product of each subarray, and return the maximum product among them.

Approach:

Run a nested loop to generate every subarray.
Calculate the product of elements in the current subarray.
Return the maximum product from these subarrays.

Below is the implementation of the above approach:

// C program to find Maximum Product Subarray
#include <stdio.h>

// Find maximum between two numbers.
int max(int num1, int num2)
{
    return (num1 > num2) ? num1 : num2;
}

/* Returns the product of max product subarray.*/
int maxSubarrayProduct(int arr[], int n)
{
    // Initializing result
    int result = arr[0];

    for (int i = 0; i < n; i++) {
        int mul = arr[i];
        // traversing in current subarray
        for (int j = i + 1; j < n; j++) {
            // updating result every time
            // to keep an eye over the maximum product
            result = max(result, mul);
            mul *= arr[j];
        }
        // updating the result for (n-1)th index.
        result = max(result, mul);
    }
    return result;
}

int main()
{
    // initialize an array
    int arr[] = { 2, 3, -2, 4 };
    // calculate the size of an array
    int n = sizeof(arr) / sizeof(arr[0]);
    // print the maximum product of subarray
    printf("Maximum Sub array product is %d ",
           maxSubarrayProduct(arr, n));
    return 0;
}

Output

Maximum Sub array product is 6

Time Complexity: O(N^2)
Auxiliary Space: O(1)

Method 2: Using Kadane’s Algorithm

We can use the Kadane’s algorithm with three variables: max_so_far, max_ending_here, and min_ending_here and iterate through the array, updating these variables to find the maximum product subarray.

Approach:

Use three variables: max_so_far, max_ending_here, and min_ending_here.
Iterate through the array and update these variables as follows:
max_ending_here = maximum(arr[i], arr[i] * max_ending_here, arr[i] * min_ending_here)
min_ending_here = minimum(arr[i], arr[i] * max_ending_here, arr[i] * min_ending_here)
Update max_so_far with the maximum value for each index.
Return max_so_far as the result.

Below is the implementation of the above approach:

// C program to solve maximum product subarray problem

#include <stdio.h>

// Function to return maximum of two integers
int max(int a, int b)
{
    // Return a if a is greater, otherwise return b
    return (a > b) ? a : b;
}

// Function to return minimum of two integers
int min(int a, int b)
{
    // Return a if a is smaller, otherwise return b
    return (a < b) ? a : b;
}

// Function to return maximum of three integers
int maxOfThree(int a, int b, int c)
{
    // Return the maximum of the three integers
    return max(a, max(b, c));
}

// Function to return minimum of three integers
int minOfThree(int a, int b, int c)
{
    // Return the minimum of the three integers
    return min(a, min(b, c));
}

// Function to find the maximum product subarray
int maxSubarrayProduct(int arr[], int n)
{
    // Initialize the maximum product ending at the first
    // element
    int max_ending_here = arr[0];
    // Initialize the minimum product ending at the first
    // element
    int min_ending_here = arr[0];
    // Initialize the maximum product found so far
    int max_so_far = arr[0];

    // Iterate through the array from the second element
    for (int i = 1; i < n; i++) {
        // Calculate the potential maximum and minimum
        // products ending at the current element
        int temp
            = maxOfThree(arr[i], arr[i] * max_ending_here,
                         arr[i] * min_ending_here);
        min_ending_here
            = minOfThree(arr[i], arr[i] * max_ending_here,
                         arr[i] * min_ending_here);
        max_ending_here = temp;

        // Update the maximum product found so far
        max_so_far = max(max_so_far, max_ending_here);
    }
    // Return the maximum product subarray
    return max_so_far;
}

int main()
{
    // Initialize the array
    int arr[] = { 2, 3, -2, 4 };
    // Calculate the number of elements in the array
    int n = sizeof(arr) / sizeof(arr[0]);

    // Print the maximum product of any subarray
    printf("Maximum Subarray product is %d\n",
           maxSubarrayProduct(arr, n));

    return 0;
}

Output

Maximum Subarray product is 6

Time Complexity: O(N)
Auxiliary Space: O(1)

Method 3: Using Traversal from Start and End of an Array

In this approach, we traverse the array, multiplying elements. If the current value is greater than the previously stored value, update it. By iterating through the array, we track the maximum product subarray ending at each position.

Approach:

Initialize two variables: max_product and current_product, both set to the first element of the array.
Traverse the array from left to right:
Update current_product by multiplying it with the current element.
Update max_product by taking the maximum of max_product and current_product.
If current_product becomes zero or negative, reset it to 1 (since a zero or negative product won’t contribute to the maximum).
Repeat the same process from right to left, maintaining another current_product and updating max_product.
Return the final max_product.

Below is the implementation of the above approach:

#include <stdio.h>

// Function to return the maximum of two integers
int max(int a, int b) { return (a > b) ? a : b; }

int maxSubarrayProduct(int arr[], int n)
{
    int max_product = arr[0];
    int current_product = 1;

    // Traverse from left to right
    for (int i = 0; i < n; i++) {
        current_product *= arr[i];
        max_product = max(max_product, current_product);

        // Reset current_product if it becomes zero
        if (current_product == 0)
            current_product = 1;
    }

    // Reset current_product for the right-to-left traversal
    current_product = 1;

    // Traverse from right to left
    for (int i = n - 1; i >= 0; i--) {
        current_product *= arr[i];
        max_product = max(max_product, current_product);

        // Reset current_product if it becomes zero
        if (current_product == 0)
            current_product = 1;
    }

    return max_product;
}

int main()
{
    // initialize the array
    int arr[] = { 2, 3, -2, 4 };
    // calculate the size of the array
    int n = sizeof(arr) / sizeof(arr[0]);
    // print the maximum product of a subarray
    printf("Maximum Subarray product is %d\n",
           maxSubarrayProduct(arr, n));
    return 0;
}

Output

Maximum Subarray product is 6

Time Complexity: O(N)
Auxiliary Space: O(1)

Reffered: https://www.geeksforgeeks.org

C Language

Related
remquo() Function in C
Kahn’s Algorithm in C Language
Counting Set bit in C
hypot() Function in C
fmod() Function in C

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	21