C ++程序中左右最大索引的最大乘积

在这个问题中，我们得到了一个数组arr []。我们的任务是创建一个程序，以计算左侧和右侧下一个更大的索引的最大乘积。

问题描述-

对于给定的数组，我们需要找到left [i] * right [i]的最大值的乘积。两个数组都定义为-

left[i] = j, such that arr[i] <’. ‘ arr[j] and i > j.
right[i] = j, such that arr[i] < arr[j] and i < j.
*The array is 1 indexed.

让我们举个例子来了解这个问题，

输入项

arr[6] = {5, 2, 3, 1, 8, 6}

输出结果

15

说明

Creating left array,
left[] = {0, 1, 1, 3, 0, 5}
right[] = {5, 3, 5, 5, 0, 0}
Index products :
1 −> 0*5 = 0
2 −> 1*3 = 3
3 −> 1*5 = 5
4 −> 3*5 = 15
5 −> 0*0 = 0
6 −> 0*5 = 0

最大乘积

15

解决方法-

在元素的左侧和右侧查找更大元素的索引的最大乘积。我们将首先找到左右的索引，并存储它们的乘积以进行比较。

现在，要找到左侧和右侧的最大元素，我们将一一检查左侧和右侧索引值中的更大元素。为了找到我们将使用堆栈。并执行以下操作，

If stack is empty −> push current index, tos = 1. Tos is top of the stack
Else if arr[i] > arr[tos] −> tos = 1.

使用此方法，我们可以找到所有大于数组左侧和右侧给定元素的元素的索引值。

示例

该程序说明了我们解决方案的工作原理，

#include <bits/stdc++.h>
using namespace std;
int* findNextGreaterIndex(int a[], int n, char ch ) {
   int* greaterIndex = new int [n];
   stack<int> index;
   if(ch == 'R'){
      for (int i = 0; i < n; ++i) {
         while (!index.empty() && a[i] > a[index.top() − 1]) {
            int indexVal = index.top();
            index.pop();
            greaterIndex[indexVal − 1] = i + 1;
         }
         index.push(i + 1);
      }
   }
   else if(ch == 'L'){
      for (int i = n − 1; i >= 0; i−−) {
         while (!index.empty() && a[i] > a[index.top() − 1]) {
            int indexVal = index.top();
            index.pop();
            greaterIndex[indexVal − 1] = i + 1;
         }
         index.push(i + 1);
      }
   }
   return greaterIndex;
}
int calcMaxGreaterIndedxProd(int arr[], int n) {
   int* left = findNextGreaterIndex(arr, n, 'L');
   int* right = findNextGreaterIndex(arr, n, 'R');
   int maxProd = −1000;
   int prod;
   for (int i = 1; i < n; i++) {
      prod = left[i]*right[i];
      if(prod > maxProd)
         maxProd = prod;
   }
   return maxProd;
}
int main() {
   int arr[] = { 5, 2, 3, 1, 8, 6};
   int n = sizeof(arr) / sizeof(arr[1]);
   cout<<"左和右下一个更大的索引的最大乘积对的是"<<calcMaxGreaterIndedxProd(arr, n);
   return 0;
}

输出结果

左和右下一个更大的索引的最大乘积对的是 15