数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 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
更新于：2020 年 9 月 9 日
111 次浏览
广告