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