Question

How to get maximum product of subarray in C++

Answer 1

#include <iostream>
 
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];
  
    std::cout << "arr[i] = " <<  arr[0] << " max_current_index = " << max_current_index << " min_current_index = " << min_current_index << " max_product " << max_product << "\n";
  
    for (int i = 1; i < len; i++) {
        int temp = max_current_index;
   
        max_current_index = std::max(arr[i], std::max(arr[i] * max_current_index, arr[i] * min_current_index));
  
        min_current_index = std::min(arr[i], std::min(arr[i] * temp, arr[i] * min_current_index));
  
        std::cout << "arr[i] = " <<  arr[i] << " max_current_index = " << max_current_index << " min_current_index = " << min_current_index << "\n";
  
        max_product = std::max(max_product, max_current_index);
  
        std::cout << "max_product = " << max_product << "\n";
    }
  
    return max_product;
}
  
int main() {
    int arr[] = { -4, 8, 2, 5, 90, 7, 0, -3, 6 }; // 8 * 2 * 5 * 90 * 7 = 50400
  
    std::cout << getMaxProductOfSubarray(arr, sizeof(arr) / sizeof(arr[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
50400
  
*/

 

70+ SQL courses for beginners and professionals