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