C ++中左右两侧的下一个更大索引的最大乘积

在本教程中，我们将讨论一个在左侧和右侧查找下一个更大索引的最大乘积的程序。

为此，我们将提供一个整数数组。我们的任务是找到具有最大左右乘积（L(i)* R(i)的元素，其中L(i)是最左侧的索引，并且大于当前元素，R(i)是右侧的最接近索引并大于当前元素）。

示例

#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
//在左侧找到更大的元素
vector<int> nextGreaterInLeft(int a[], int n) {
   vector<int> left_index(MAX, 0);
   stack<int> s;
   for (int i = n - 1; i >= 0; i--) {
      while (!s.empty() && a[i] > a[s.top() - 1]) {
         int r = s.top();
         s.pop();
         left_index[r - 1] = i + 1;
      }
      s.push(i + 1);
   }
   return left_index;
}
//在右侧找到更大的元素
vector<int> nextGreaterInRight(int a[], int n) {
   vector<int> right_index(MAX, 0);
   stack<int> s;
   for (int i = 0; i < n; ++i) {
      while (!s.empty() && a[i] > a[s.top() - 1]) {
         int r = s.top();
         s.pop();
         right_index[r - 1] = i + 1;
      }
      s.push(i + 1);
   }
   return right_index;
}
//寻找最大的LR产品
int LRProduct(int arr[], int n) {
   vector<int> left = nextGreaterInLeft(arr, n);
   vector<int> right = nextGreaterInRight(arr, n);
   int ans = -1;
   for (int i = 1; i <= n; i++) {
      ans = max(ans, left[i] * right[i]);
   }
   return ans;
}
int main() {
   int arr[] = { 5, 4, 3, 4, 5 };
   int n = sizeof(arr) / sizeof(arr[1]);
   cout << LRProduct(arr, n);
   return 0;
}

输出结果

8