C Online Compiler
Example: Maximum Product Subarray (Optimized DP) in C
C
C++
C#
Java
Python
PHP
main.c
STDIN
Run
// Maximum Product Subarray (Optimized DP) #include
#include
// For INT_MIN #include
// 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; }
Output
Clear
ADVERTISEMENTS