Maximum Product Subarray in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Maximum Product Subarray Calculation

What is the output of the following C code that finds the maximum product of a contiguous subarray?

DSA C

int maxProduct(int* nums, int numsSize) {
    int max_so_far = nums[0];
    int min_so_far = nums[0];
    int result = nums[0];
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] < 0) {
            int temp = max_so_far;
            max_so_far = min_so_far;
            min_so_far = temp;
        }
        max_so_far = nums[i] > max_so_far * nums[i] ? nums[i] : max_so_far * nums[i];
        min_so_far = nums[i] < min_so_far * nums[i] ? nums[i] : min_so_far * nums[i];
        if (max_so_far > result) result = max_so_far;
    }
    return result;
}

int main() {
    int arr[] = {2, 3, -2, 4};
    int size = sizeof(arr) / sizeof(arr[0]);
    int max_product = maxProduct(arr, size);
    printf("%d\n", max_product);
    return 0;
}

A -2

B 4

C 8

D 6

💡 Hint

Track max and min products at each step, especially when encountering negative numbers.

The maximum product subarray is [2, 3] with product 6. The code keeps track of max and min products to handle negatives.

❓ Predict Output

intermediate

Result of Maximum Product Subarray with Negative Numbers

What will be printed by this C program that calculates the maximum product subarray?

DSA C

int maxProduct(int* nums, int numsSize) {
    int max_so_far = nums[0];
    int min_so_far = nums[0];
    int result = nums[0];
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] < 0) {
            int temp = max_so_far;
            max_so_far = min_so_far;
            min_so_far = temp;
        }
        max_so_far = nums[i] > max_so_far * nums[i] ? nums[i] : max_so_far * nums[i];
        min_so_far = nums[i] < min_so_far * nums[i] ? nums[i] : min_so_far * nums[i];
        if (max_so_far > result) result = max_so_far;
    }
    return result;
}

int main() {
    int arr[] = {-2, 0, -1};
    int size = sizeof(arr) / sizeof(arr[0]);
    int max_product = maxProduct(arr, size);
    printf("%d\n", max_product);
    return 0;
}

A -2

B -1

C 0

D 2

💡 Hint

Zero resets the product, consider subarrays including zero.

The maximum product subarray is [0] with product 0. Negative numbers and zero reset the product tracking.

🧠 Conceptual

advanced

Understanding the Role of min_so_far in Maximum Product Subarray

Why does the algorithm keep track of the minimum product so far (min_so_far) when finding the maximum product subarray?

A Because minimum product helps to find the smallest subarray length.

B Because the minimum product can become maximum if multiplied by a negative number.

C Because minimum product stores the smallest element in the array.

D Because minimum product is used to count negative numbers in the array.

💡 Hint

Think about how negative numbers affect multiplication.

Multiplying two negative numbers can produce a positive number, so tracking the minimum product helps find a larger maximum product later.

🔧 Debug

advanced

Identify the Bug in Maximum Product Subarray Code

What error will this C code produce when run, and why?

DSA C

int maxProduct(int* nums, int numsSize) {
    int max_so_far = nums[0];
    int min_so_far = nums[0];
    int result = nums[0];
    for (int i = 1; i <= numsSize; i++) {
        if (nums[i] < 0) {
            int temp = max_so_far;
            max_so_far = min_so_far;
            min_so_far = temp;
        }
        max_so_far = nums[i] > max_so_far * nums[i] ? nums[i] : max_so_far * nums[i];
        min_so_far = nums[i] < min_so_far * nums[i] ? nums[i] : min_so_far * nums[i];
        if (max_so_far > result) result = max_so_far;
    }
    return result;
}

int main() {
    int arr[] = {2, 3, -2, 4};
    int size = sizeof(arr) / sizeof(arr[0]);
    int max_product = maxProduct(arr, size);
    printf("%d\n", max_product);
    return 0;
}

A Runtime error due to accessing out-of-bounds array index.

B Syntax error because of missing semicolon.

C Returns incorrect maximum product 4.

D Compiles and runs correctly, output 6.

💡 Hint

Check the loop condition carefully.

The loop runs with i <= numsSize, which accesses nums[numsSize], out of array bounds causing runtime error.

🚀 Application

expert

Maximum Product Subarray with Zero and Negative Numbers

Given the array [1, -2, -3, 0, 7, -8, -2], what is the maximum product of any contiguous subarray?

A 112

B 48

C 0

D 14

💡 Hint

Consider subarrays before and after zero, and how negatives multiply.

The maximum product subarray is [7, -8, -2] with product 7 * -8 * -2 = 112.