Example: Maximum Product Subarray (Optimized DP) in C

// 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;
}