Finding Maximum Product Sub-array in a Given Array in C

Understanding Maximum Product Sub-array

This task involves finding the contiguous sub-array that has the maximum product.

We will explore three different methods to achieve this in C.

Method 1: Using Brute Force

This method calculates the product of all possible sub-arrays and finds the maximum.

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

void max_product_subarray(int arr[], int n) {
    int max_product = INT_MIN;
    for (int i = 0; i < n; i++) {
        int product = 1;
        for (int j = i; j < n; j++) {
            product *= arr[j];
            if (product > max_product)
                max_product = product;
        }
    }
    printf("Maximum Product: %d\n", max_product);
}

int main() {
    int arr[] = {2, 3, -2, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    max_product_subarray(arr, n);
    return 0;
}

Output:
Maximum Product: 6

Method 2: Using Dynamic Programming (Kadane's Variation)

This method keeps track of the maximum and minimum products at each step.

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

void max_product_subarray(int arr[], int n) {
    int max_product = arr[0], min_product = arr[0], result = arr[0];
    for (int i = 1; i < n; i++) {
        int temp = max_product;
        max_product = (arr[i] > arr[i] * max_product) ? (arr[i] > arr[i] * min_product ? arr[i] : arr[i] * min_product) : arr[i] * max_product;
        min_product = (arr[i] < arr[i] * temp) ? (arr[i] < arr[i] * min_product ? arr[i] : arr[i] * min_product) : arr[i] * temp;
        if (max_product > result)
            result = max_product;
    }
    printf("Maximum Product: %d\n", result);
}

int main() {
    int arr[] = {2, 3, -2, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    max_product_subarray(arr, n);
    return 0;
}

Output:
Maximum Product: 6

Method 3: Using a Single Pass Approach

This method efficiently finds the maximum product sub-array using a single pass.

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

void max_product_subarray(int arr[], int n) {
    int max_product = arr[0], min_product = arr[0], result = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] < 0) {
            int temp = max_product;
            max_product = min_product;
            min_product = temp;
        }
        max_product = (arr[i] > arr[i] * max_product) ? arr[i] : arr[i] * max_product;
        min_product = (arr[i] < arr[i] * min_product) ? arr[i] : arr[i] * min_product;
        if (max_product > result)
            result = max_product;
    }
    printf("Maximum Product: %d\n", result);
}

int main() {
    int arr[] = {2, 3, -2, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    max_product_subarray(arr, n);
    return 0;
}

Output:
Maximum Product: 6