Question

How to get maximum product of subarray in C

Answer 1

#include <stdio.h>
 
int min(int x, int y) {
    return (x < y) ? x : y;
}
 
int max(int x, int y) {
    return (x > y) ? x : y;
}
 
int getMaxProductOfSubarray(int arr[], int len) {
    if (len == 0) {
        return 0;
    }
 
    int max_current_index = arr[0], min_current_index = arr[0], max_product = arr[0];
 
    printf("arr[i] = %d max_current_index = %d  min_current_index = %d max_product = %d\n", arr[0], max_current_index, min_current_index, max_product);
 
    for (int i = 1; i < len; i++) {
        int temp = max_current_index;
  
        max_current_index = max(arr[i], max(arr[i] * max_current_index, arr[i] * min_current_index));
 
        min_current_index = min(arr[i], min(arr[i] * temp, arr[i] * min_current_index));
 
        printf("arr[i] = %d max_current_index = %d  min_current_index = %d\n", arr[i], max_current_index, min_current_index);
 
        max_product = max(max_product, max_current_index);
 
        printf("max_product = %d\n", max_product);
    }
 
    return max_product;
}
 
int main() {
    int arr[] = { -4, 8, 2, 5, 90, 7, 0, -3, 6 }; // 8 * 2 * 5 * 90 * 7 = 50400
 
    printf("maximum product = %d", getMaxProductOfSubarray(arr, sizeof(arr) / sizeof(arr[0])));
 
    return 0;
}
 
 
 
 
/*
run:
 
arr[i] = -4 max_current_index = -4  min_current_index = -4 max_product = -4
arr[i] = 8 max_current_index = 8  min_current_index = -32
max_product = 8
arr[i] = 2 max_current_index = 16  min_current_index = -64
max_product = 16
arr[i] = 5 max_current_index = 80  min_current_index = -320
max_product = 80
arr[i] = 90 max_current_index = 7200  min_current_index = -28800
max_product = 7200
arr[i] = 7 max_current_index = 50400  min_current_index = -201600
max_product = 50400
arr[i] = 0 max_current_index = 0  min_current_index = 0
max_product = 50400
arr[i] = -3 max_current_index = 0  min_current_index = -3
max_product = 50400
arr[i] = 6 max_current_index = 6  min_current_index = -18
max_product = 50400
maximum product = 50400
 
*/

 

70+ SQL courses for beginners and professionals