Maximum Product Subarray in DSA C - Build from Scratch

Maximum Product Subarray

📖 Scenario: You are working on a financial analysis tool that needs to find the maximum product of a contiguous subarray within a list of daily stock returns. This helps identify the period with the highest compounded return.

🎯 Goal: Build a program that finds the maximum product of any contiguous subarray in a given array of integers.

📋 What You'll Learn

Create an integer array called nums with the exact values: {2, 3, -2, 4}

Create an integer variable called n that stores the length of nums

Create integer variables maxProd, minProd, and result to track the maximum product, minimum product, and final result respectively

Use a for loop with variable i from 1 to n - 1 to iterate over nums

Inside the loop, update maxProd and minProd by considering nums[i], maxProd * nums[i], and minProd * nums[i]

Update result to be the maximum of itself and maxProd

Print the value of result at the end

💡 Why This Matters

🌍 Real World

Finding maximum product subarrays helps in financial analysis to identify periods of highest compounded returns or in signal processing to find segments with maximum gain.

💼 Career

This problem is common in technical interviews and helps develop skills in array manipulation, dynamic programming, and handling edge cases with negative numbers.

1

Create the input array

Create an integer array called nums with the exact values {2, 3, -2, 4} and an integer variable n that stores the length of nums.

DSA C

# Create the array nums and variable n
// Your code here

Hint

Use int nums[] = {2, 3, -2, 4}; to create the array and int n = sizeof(nums) / sizeof(nums[0]); to get its length.

2

Initialize tracking variables

Create integer variables maxProd, minProd, and result. Initialize all three to the first element of nums.

DSA C

#include 

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

    // Initialize maxProd, minProd, and result to nums[0]
    // Your code here

    return 0;
}

Hint

Set maxProd, minProd, and result equal to nums[0].

3

Implement the main loop to find maximum product

Use a for loop with variable i from 1 to n - 1 to iterate over nums. Inside the loop, create an integer tempMax to store the current maxProd. Update maxProd to the maximum of nums[i], maxProd * nums[i], and minProd * nums[i]. Update minProd to the minimum of nums[i], tempMax * nums[i], and minProd * nums[i]. Then update result to the maximum of result and maxProd. Use the helper functions max and min defined below.

DSA C

#include 

int max(int a, int b) {
    return (a > b) ? a : b;
}

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

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

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

    // Use a for loop from i = 1 to n - 1
    // Inside the loop, update maxProd, minProd, and result
    // Your code here

    return 0;
}

Hint

Remember to save the old maxProd in tempMax before updating. Use helper functions max3 and min3 to find max and min of three values.

4

Print the maximum product result

Print the value of result using printf.

DSA C

#include 

int max(int a, int b) {
    return (a > b) ? a : b;
}

int min(int a, int b) {
    return (a  result) {
            result = maxProd;
        }
    }

    // Print the result
    // Your code here

    return 0;
}

Hint

Use printf("%d\n", result); to print the maximum product.