Tích tối đa của các chỉ mục lớn hơn tiếp theo ở bên trái và bên phải trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm tích số tối đa của các chỉ mục lớn hơn tiếp theo ở bên trái và bên phải.

Đối với điều này, chúng tôi sẽ được cung cấp với một mảng các số nguyên. Nhiệm vụ của chúng ta là tìm phần tử có tích Trái-Phải lớn nhất (L (i) * R (i) trong đó L (i) là chỉ số gần nhất ở phía bên trái và lớn hơn phần tử hiện tại và R (i) là chỉ số gần nhất ở phía bên phải và lớn hơn phần tử hiện tại).

Ví dụ

#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;
}

Đầu ra

8