Dada una array a[1..N]. Para cada elemento en la posición i (1 <= i <= N). Dónde
- L(i) se define como el índice j más cercano tal que j < i y a[j] > a[i]. Si no existe tal j, entonces L(i) = 0 .
- R(i) se define como el índice k más cercano tal que k > iy a[k] > a[i]. Si no existe tal k entonces R(i) = 0 .
LRProducto(i) = L(i)*R(i) .
Necesitamos encontrar un índice con LRProduct máximo
Ejemplos:
Entrada: 1 1 1 1 0 1 1 1 1 1
Salida: 24
Para {1, 1, 1, 1, 0, 1, 1, 1, 1, 1} todos los elementos son iguales excepto 0. Entonces solo para cero existen elemento mayor y para otros será cero. para cero, el cuarto elemento de la izquierda es el más cercano y mayor que cero y el sexto elemento de la derecha es el más cercano y mayor. entonces el producto máximo
será 4*6 = 24.Entrada: 5 4 3 4 5
Salida: 8
Para {5, 4, 3, 4, 5}, L[] = {0, 1, 2, 1, 0} y R[]
= {0, 5, 4, 5, 0},
LRProduct = {0, 5, 8, 5, 0} y el máximo en esto es 8.
Nota: Tomando el índice inicial como 1 para encontrar el producto LR.
Este problema se basa en Next Greater Element .
Desde la posición actual, necesitamos encontrar el elemento mayor más cercano en su lado izquierdo y derecho.
Entonces, para encontrar el siguiente elemento mayor, usamos una pila desde la izquierda y otra desde la derecha. Simplemente estamos verificando qué elemento es mayor y almacenando su índice en la posición especificada.
1- si la pila está vacía, presione el índice actual.
2- si la pila no está vacía
… a) si el elemento actual es mayor que el elemento superior, almacene el índice del elemento actual en el índice del elemento superior.
Haga esto, una vez que atraviese el elemento de array desde la izquierda y una vez desde la derecha y forme la array izquierda y derecha, luego, multiplíquelos para encontrar el valor máximo del producto.
C++
// C++ program to find the max
// LRproduct[i] among all i
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
// function to find just next greater
// element in 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--) {
// checking if current element is greater than top
while (!s.empty() && a[i] > a[s.top() - 1]) {
int r = s.top();
s.pop();
// on index of top store the current element
// index which is just greater than top element
left_index[r - 1] = i + 1;
}
// else push the current element in stack
s.push(i + 1);
}
return left_index;
}
// function to find just next greater element
// in 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) {
// checking if current element is greater than top
while (!s.empty() && a[i] > a[s.top() - 1]) {
int r = s.top();
s.pop();
// on index of top store the current element
// index which is just greater than top element
// stored index should be start with 1
right_index[r - 1] = i + 1;
}
// else push the current element in stack
s.push(i + 1);
}
return right_index;
}
// Function to find maximum LR product
int LRProduct(int arr[], int n)
{
// for each element storing the index of just
// greater element in left side
vector<int> left = nextGreaterInLeft(arr, n);
// for each element storing the index of just
// greater element in right side
vector<int> right = nextGreaterInRight(arr, n);
int ans = -1;
for (int i = 1; i <= n; i++) {
// finding the max index product
ans = max(ans, left[i] * right[i]);
}
return ans;
}
// Drivers code
int main()
{
int arr[] = { 5, 4, 3, 4, 5 };
int n = sizeof(arr) / sizeof(arr[1]);
cout << LRProduct(arr, n);
return 0;
}
Java
// Java program to find the
// max LRproduct[i] among all i
import java.io.*;
import java.util.*;
class GFG
{
static int MAX = 1000;
// function to find just next
// greater element in left side
static int[] nextGreaterInLeft(int []a,
int n)
{
int []left_index = new int[MAX];
Stack<Integer> s = new Stack<Integer>();
for (int i = n - 1; i >= 0; i--)
{
// checking if current
// element is greater than top
while (s.size() != 0 &&
a[i] > a[s.peek() - 1])
{
int r = s.peek();
s.pop();
// on index of top store
// the current element
// index which is just
// greater than top element
left_index[r - 1] = i + 1;
}
// else push the current
// element in stack
s.push(i + 1);
}
return left_index;
}
// function to find just next
// greater element in right side
static int[] nextGreaterInRight(int []a,
int n)
{
int []right_index = new int[MAX];
Stack<Integer> s = new Stack<Integer>();
for (int i = 0; i < n; ++i) {
// checking if current element
// is greater than top
while (s.size() != 0 &&
a[i] > a[s.peek() - 1])
{
int r = s.peek();
s.pop();
// on index of top store
// the current element index
// which is just greater than
// top element stored index
// should be start with 1
right_index[r - 1] = i + 1;
}
// else push the current
// element in stack
s.push(i + 1);
}
return right_index;
}
// Function to find
// maximum LR product
static int LRProduct(int []arr, int n)
{
// for each element storing
// the index of just greater
// element in left side
int []left = nextGreaterInLeft(arr, n);
// for each element storing
// the index of just greater
// element in right side
int []right = nextGreaterInRight(arr, n);
int ans = -1;
for (int i = 1; i <= n; i++)
{
// finding the max
// index product
ans = Math.max(ans, left[i] *
right[i]);
}
return ans;
}
// Driver code
public static void main(String args[])
{
int []arr = new int[]{ 5, 4, 3, 4, 5 };
int n = arr.length;
System.out.print(LRProduct(arr, n));
}
}
// This code is contributed by
// Manish Shaw(manishshaw1)
Python3
# Python3 program to find the # max LRproduct[i] among all i # Method to find the next greater # value in left side def nextGreaterInLeft(a): left_index = [0] * len(a) s = [] for i in range(len(a)): # Checking if current # element is greater than top while len(s) != 0 and a[i] >= a[s[-1]]: # Pop the element till we can't # get the larger value then # the current value s.pop() if len(s) != 0: left_index[i] = s[-1] else: left_index[i] = 0 # Else push the element in the stack s.append(i) return left_index # Method to find the next # greater value in right def nextGreaterInRight(a): right_index = [0] * len(a) s = [] for i in range(len(a) - 1, -1, -1): # Checking if current element # is greater than top while len(s) != 0 and a[i] >= a[s[-1]]: # Pop the element till we can't # get the larger value then # the current value s.pop() if len(s) != 0: right_index[i] = s[-1] else: right_index[i] = 0 # Else push the element in the stack s.append(i) return right_index def LRProduct(arr): # For each element storing # the index of just greater # element in left side left = nextGreaterInLeft(arr) # For each element storing # the index of just greater # element in right side right = nextGreaterInRight(arr) ans = -1 # As we know the answer will # belong to the range from # 1st index to second last index. # Because for 1st index left # will be 0 and for last # index right will be 0 for i in range(1, len(left) - 1): if left[i] == 0 or right[i] == 0: # Finding the max index product ans = max(ans, 0) else: temp = (left[i] + 1) * (right[i] + 1) # Finding the max index product ans = max(ans, temp) return ans # Driver Code arr = [ 5, 4, 3, 4, 5 ] print(LRProduct(arr)) # This code is contributed by Mohit Pathneja
C#
// C# program to find the max LRproduct[i]
// among all i
using System;
using System.Collections.Generic;
class GFG {
static int MAX = 1000;
// function to find just next greater
// element in left side
static int[] nextGreaterInLeft(int []a, int n)
{
int []left_index = new int[MAX];
Stack<int> s = new Stack<int>();
for (int i = n - 1; i >= 0; i--) {
// checking if current element is
// greater than top
while (s.Count != 0 && a[i] > a[s.Peek() - 1])
{
int r = s.Peek();
s.Pop();
// on index of top store the current
// element index which is just greater
// than top element
left_index[r - 1] = i + 1;
}
// else push the current element in stack
s.Push(i + 1);
}
return left_index;
}
// function to find just next greater element
// in right side
static int[] nextGreaterInRight(int []a, int n)
{
int []right_index = new int[MAX];
Stack<int> s = new Stack<int>();
for (int i = 0; i < n; ++i) {
// checking if current element is
// greater than top
while (s.Count != 0 && a[i] > a[s.Peek() - 1])
{
int r = s.Peek();
s.Pop();
// on index of top store the current
// element index which is just greater
// than top element stored index should
// be start with 1
right_index[r - 1] = i + 1;
}
// else push the current element in stack
s.Push(i + 1);
}
return right_index;
}
// Function to find maximum LR product
static int LRProduct(int []arr, int n)
{
// for each element storing the index of just
// greater element in left side
int []left = nextGreaterInLeft(arr, n);
// for each element storing the index of just
// greater element in right side
int []right = nextGreaterInRight(arr, n);
int ans = -1;
for (int i = 1; i <= n; i++) {
// finding the max index product
ans = Math.Max(ans, left[i] * right[i]);
}
return ans;
}
// Drivers code
static void Main()
{
int []arr = new int[]{ 5, 4, 3, 4, 5 };
int n = arr.Length;
Console.Write(LRProduct(arr, n));
}
}
// This code is contributed by Manish Shaw
Javascript
<script>
// Javascript program to find the max LRproduct[i] among all i
let MAX = 1000;
// function to find just next greater
// element in left side
function nextGreaterInLeft(a, n)
{
let left_index = new Array(MAX);
left_index.fill(0);
let s = [];
for (let i = n - 1; i >= 0; i--) {
// checking if current element is
// greater than top
while (s.length != 0 && a[i] > a[s[s.length - 1] - 1])
{
let r = s[s.length - 1];
s.pop();
// on index of top store the current
// element index which is just greater
// than top element
left_index[r - 1] = i + 1;
}
// else push the current element in stack
s.push(i + 1);
}
return left_index;
}
// function to find just next greater element
// in right side
function nextGreaterInRight(a, n)
{
let right_index = new Array(MAX);
right_index.fill(0);
let s = [];
for (let i = 0; i < n; ++i) {
// checking if current element is
// greater than top
while (s.length != 0 && a[i] > a[s[s.length - 1] - 1])
{
let r = s[s.length - 1];
s.pop();
// on index of top store the current
// element index which is just greater
// than top element stored index should
// be start with 1
right_index[r - 1] = i + 1;
}
// else push the current element in stack
s.push(i + 1);
}
return right_index;
}
// Function to find maximum LR product
function LRProduct(arr, n)
{
// for each element storing the index of just
// greater element in left side
let left = nextGreaterInLeft(arr, n);
// for each element storing the index of just
// greater element in right side
let right = nextGreaterInRight(arr, n);
let ans = -1;
for (let i = 1; i <= n; i++) {
// finding the max index product
ans = Math.max(ans, left[i] * right[i]);
}
return ans;
}
let arr = [ 5, 4, 3, 4, 5 ];
let n = arr.length;
document.write(LRProduct(arr, n));
// This code is contributed by suresh07.
</script>
Producción:
8
Análisis de Complejidad:
Complejidad de tiempo: O(n)
Complejidad espacial: O(n)
Método 2: Reducir el espacio utilizado usando solo una array para almacenar el máximo izquierdo y derecho.
Acercarse:
Requisito previo: https://www.geeksforgeeks.org/next-greater-element/
- Para encontrar el siguiente elemento mayor a la izquierda, usamos una pila desde la izquierda, y la misma pila se usa para multiplicar el índice del elemento más grande de la derecha con el índice del elemento más grande de la izquierda.
- La función maxProduct( ) se usa para devolver el producto máximo al iterar la array resultante.
C++
// C++ program to find max LR product
#include <bits/stdc++.h>
using namespace std;
stack<int> mystack;
// To find greater element to left
void nextGreaterToLeft(int arr[], int res[], int N) {
mystack.push(0);
res[0] = 0;
// iterate through the array
for(int i = 1; i < N; i++) {
while(mystack.size() > 0 && arr[mystack.top()] <= arr[i])
mystack.pop();
// place the index to the left in the resultant array
res[i] = (mystack.size() == 0) ? 0 : mystack.top()+1;
mystack.push(i);
}
}
//// To find greater element to right
void nextGreaterToRight(int arr[], int res[], int N) {
mystack = stack<int>();
int n = N;
mystack.push(n-1);
res[n-1] *= 0;
// iterate through the array in the reverse order
for(int i=n - 2 ; i >= 0; i--) {
while(mystack.size() > 0 && arr[mystack.top()] <= arr[i])
mystack.pop();
//multiply the index to the right with the index to the left
//in the resultant array
res[i] = (mystack.size() == 0) ? res[i]*0 : res[i]*(mystack.top()+1);
mystack.push(i);
}
}
//function to return the max value in the resultant array
int maxProduct(int arr[], int res[], int N) {
nextGreaterToLeft(arr,res, N); //to find left max
nextGreaterToRight(arr,res, N); //to find right max
int Max = res[0];
for(int i = 1; i < N; i++){
Max = max(Max, res[i]);
}
return Max;
}
int main()
{
int arr[] = {5, 4, 3, 4, 5};
int N = sizeof(arr) / sizeof(arr[0]);
int res[N];
int maxprod = maxProduct(arr, res, N);
cout << maxprod << endl;
return 0;
}
// This code is contributed by decode2207.
Java
//java program to find max LR product
import java.util.*;
public class GFG {
Stack<Integer> mystack = new Stack<>();
//To find greater element to left
void nextGreaterToLeft(int[] arr,int[] res) {
mystack.push(0);
res[0] = 0;
//iterate through the array
for(int i=1;i<arr.length;i++) {
while(!mystack.isEmpty() && arr[mystack.peek()] <= arr[i])
mystack.pop();
//place the index to the left in the resultant array
res[i] = (mystack.isEmpty()) ? 0 : mystack.peek()+1;
mystack.push(i);
}
}
////To find greater element to right
void nextGreaterToRight(int[] arr,int[] res) {
mystack.clear();
int n = arr.length;
mystack.push(n-1);
res[n-1] *= 0;
//iterate through the array in the reverse order
for(int i=n-2;i>=0;i--) {
while(!mystack.isEmpty() && arr[mystack.peek()] <= arr[i])
mystack.pop();
//multiply the index to the right with the index to the left
//in the resultant array
res[i] = (mystack.isEmpty()) ? res[i]*0 : res[i]*(mystack.peek()+1);
mystack.push(i);
}
}
//function to return the max value in the resultant array
int maxProduct(int[] arr,int[] res) {
nextGreaterToLeft(arr,res); //to find left max
nextGreaterToRight(arr,res); //to find right max
int max = res[0];
for(int i = 1;i<res.length;i++){
max = Math.max(max, res[i]);
}
return max;
}
//Driver function
public static void main(String args[]) {
GFG obj = new GFG();
int arr[] = {5, 4, 3, 4, 5};
int res[] = new int[arr.length];
int maxprod = obj.maxProduct(arr, res);
System.out.println(maxprod);
}
}
//this method is contributed by Likhita AVL
Python3
# Python3 program to find max LR product mystack = [] # To find greater element to left def nextGreaterToLeft(arr, res): mystack.append(0) res[0] = 0 # iterate through the array for i in range(1, len(arr)): while(len(mystack) > 0 and arr[mystack[-1]] <= arr[i]): mystack.pop() # place the index to the left in the resultant array if (len(mystack) == 0): res[i] = 0 else: res[i] = mystack[-1]+1 mystack.append(i) # To find greater element to right def nextGreaterToRight(arr, res): mystack = [] n = len(arr) mystack.append(n-1) res[n-1] *= 0 # iterate through the array in the reverse order for i in range(n - 2, -1, -1): while(len(mystack) > 0 and arr[mystack[-1]] <= arr[i]): mystack.pop() # multiply the index to the right with the index to the left # in the resultant array if (len(mystack) == 0): res[i] = res[i]*0 else : res[i] = res[i]*(mystack[-1]+1) mystack.append(i) # function to return the max value in the resultant array def maxProduct(arr, res): nextGreaterToLeft(arr,res) #to find left max nextGreaterToRight(arr,res) #to find right max Max = res[0] for i in range(1, len(res)): Max = max(Max, res[i]) return Max # Driver code arr = [5, 4, 3, 4, 5] res = [0]*(len(arr)) maxprod = maxProduct(arr, res) print(maxprod) # This code is contributed by mukesh07.
C#
// C# program to find max LR product
using System;
using System.Collections;
class GFG {
static Stack mystack = new Stack();
//To find greater element to left
static void nextGreaterToLeft(int[] arr,int[] res) {
mystack.Push(0);
res[0] = 0;
//iterate through the array
for(int i=1;i<arr.Length;i++) {
while(mystack.Count > 0 && arr[(int)mystack.Peek()] <= arr[i])
mystack.Pop();
//place the index to the left in the resultant array
res[i] = (mystack.Count == 0) ? 0 : (int)mystack.Peek()+1;
mystack.Push(i);
}
}
////To find greater element to right
static void nextGreaterToRight(int[] arr,int[] res) {
mystack = new Stack();
int n = arr.Length;
mystack.Push(n-1);
res[n-1] *= 0;
//iterate through the array in the reverse order
for(int i = n - 2; i >= 0; i--) {
while(mystack.Count == 0 && arr[(int)mystack.Peek()] <= arr[i])
mystack.Pop();
//multiply the index to the right with the index to the left
//in the resultant array
res[i] = (mystack.Count == 0) ? res[i]*0 : res[i]*((int)mystack.Peek()+1);
mystack.Push(i);
}
}
//function to return the max value in the resultant array
static int maxProduct(int[] arr,int[] res) {
nextGreaterToLeft(arr, res); //to find left max
nextGreaterToRight(arr, res); //to find right max
int max = res[0];
for(int i = 1; i < res.Length; i++){
max = Math.Max(max, res[i]);
}
return max;
}
static void Main() {
int[] arr = {5, 4, 3, 4, 5};
int[] res = new int[arr.Length];
int maxprod = maxProduct(arr, res);
Console.WriteLine(maxprod);
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// Javascript program to find max LR product
let mystack = [];
// To find greater element to left
function nextGreaterToLeft(arr, res) {
mystack.push(0);
res[0] = 0;
// iterate through the array
for(let i = 1; i < arr.length; i++) {
while(mystack.length > 0 && arr[mystack[mystack.length - 1]] <= arr[i])
mystack.pop();
// place the index to the left in the resultant array
res[i] = (mystack.length == 0) ? 0 : mystack[mystack.length - 1]+1;
mystack.push(i);
}
}
//// To find greater element to right
function nextGreaterToRight(arr, res) {
mystack = [];
let n = arr.length;
mystack.push(n-1);
res[n-1] *= 0;
// iterate through the array in the reverse order
for(let i = n - 2; i >= 0; i--) {
while(mystack.length > 0 && arr[mystack[mystack.length - 1]] <= arr[i])
mystack.pop();
// multiply the index to the right with the index to the left
// in the resultant array
res[i] = (mystack.length == 0) ? res[i]*0 : res[i]*(mystack[mystack.length - 1]+1);
mystack.push(i);
}
}
// function to return the max value in the resultant array
function maxProduct(arr, res) {
nextGreaterToLeft(arr,res); //to find left max
nextGreaterToRight(arr,res); //to find right max
let max = res[0];
for(let i = 1;i<res.length;i++){
max = Math.max(max, res[i]);
}
return max;
}
let arr = [5, 4, 3, 4, 5];
let res = new Array(arr.length);
let maxprod = maxProduct(arr, res);
document.write(maxprod);
// This code is contributed by divyesh072019.
</script>
Producción
8
Análisis de Complejidad:
Complejidad de tiempo: O(n)
Complejidad espacial: O(n)
Publicación traducida automáticamente
Artículo escrito por Ravi_Maurya y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA