Home » Data Structure

Find the maximum product formed by multiplying numbers of an increasing subsequence of an array

Here is the implementation of find the maximum product formed by multiplying numbers of an increasing subsequence of an array in C:

C program to find the maximum product formed by multiplying numbers of an increasing subsequence of an array

#include <stdio.h>

// Function to find the maximum product of an
// increasing subsequence
int maxProductIncreasingSubsequence(int arr[], int n) {
  int maxProduct[n];

  // Initialize the maxProduct array
  // with the elements of array
  for (int i = 0; i < n; i++) {
    maxProduct[i] = arr[i];
  }

  int maxOverall = arr[0];

  // Fill the maxProduct array
  for (int i = 1; i < n; i++) {
    for (int j = 0; j < i; j++) {
      if (arr[i] > arr[j] && maxProduct[i] < maxProduct[j] * arr[i]) {
        maxProduct[i] = maxProduct[j] * arr[i];
      }
    }
    if (maxProduct[i] > maxOverall) {
      maxOverall = maxProduct[i];
    }
  }

  return maxOverall;
}

int main() {
  int arr[] = {3, 100, 4, 5, 150, 6};
  int n = sizeof(arr) / sizeof(arr[0]);
  int result = maxProductIncreasingSubsequence(arr, n);
  printf("The maximum product of an increasing subsequence is: %d\n", result);
  return 0;
}

Output

The maximum product of an increasing subsequence is: 45000