C++の左右の次に大きいインデックスの最大積

このチュートリアルでは、左右で次に大きいインデックスの最大積を見つけるプログラムについて説明します。

このために、整数の配列が提供されます。私たちのタスクは、最大の左右積（L（i）* R（i）を持つ要素を見つけることです。ここで、L（i）は左側の最も近いインデックスであり、現在の要素よりも大きく、R（i）は右側の最も近いインデックスです。現在の要素よりも大きい）。

例

#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
//finding greater element on left side
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;
}
//finding greater element on right side
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;
}
//finding maximum LR product
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