資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告