Dada una array arr[], encuentre el máximo j – i tal que arr[j] > arr[i].
Ejemplos:
Input: {34, 8, 10, 3, 2, 80, 30, 33, 1}
Output: 6 (j = 7, i = 1)
Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}
Output: 8 ( j = 8, i = 0)
Input: {1, 2, 3, 4, 5, 6}
Output: 5 (j = 5, i = 0)
Input: {6, 5, 4, 3, 2, 1}
Output: -1
Método 1 (Simple pero ineficiente): Ejecute dos bucles. En el bucle exterior, elija elementos uno por uno desde la izquierda. En el bucle interno, compare el elemento seleccionado con los elementos que comienzan desde el lado derecho. Detenga el ciclo interno cuando vea un elemento mayor que el elemento seleccionado y siga actualizando el ji máximo hasta el momento.
C++
// CPP program for the above approach
#include <bits/stdc++.h>
using namespace std;
/* For a given array arr[],
returns the maximum j – i such
that arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
int maxDiff = -1;
int i, j;
for (i = 0; i < n; ++i) {
for (j = n - 1; j > i; --j) {
if (arr[j] > arr[i] && maxDiff < (j - i))
maxDiff = j - i;
}
}
return maxDiff;
}
int main()
{
int arr[] = { 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
int maxDiff = maxIndexDiff(arr, n);
cout << "\n" << maxDiff;
return 0;
}
// This code is contributed
// by Akanksha Rai(Abby_akku)
C
// C program for the above approach
#include <stdio.h>
/* For a given array arr[],
returns the maximum j – i such
that arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
int maxDiff = -1;
int i, j;
for (i = 0; i < n; ++i) {
for (j = n - 1; j > i; --j) {
if (arr[j] > arr[i] && maxDiff < (j - i))
maxDiff = j - i;
}
}
return maxDiff;
}
int main()
{
int arr[] = { 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
int maxDiff = maxIndexDiff(arr, n);
printf("\n %d", maxDiff);
getchar();
return 0;
}
Java
// Java program for the above approach
class FindMaximum {
/* For a given array arr[],
returns the maximum j-i such
that arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
int maxDiff = -1;
int i, j;
for (i = 0; i < n; ++i) {
for (j = n - 1; j > i; --j) {
if (arr[j] > arr[i] && maxDiff < (j - i))
maxDiff = j - i;
}
}
return maxDiff;
}
/* Driver program to test above functions */
public static void main(String[] args)
{
FindMaximum max = new FindMaximum();
int arr[] = { 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 };
int n = arr.length;
int maxDiff = max.maxIndexDiff(arr, n);
System.out.println(maxDiff);
}
}
Python3
# Python3 program to find the maximum # j – i such that arr[j] > arr[i] # For a given array arr[], returns # the maximum j – i such that # arr[j] > arr[i] def maxIndexDiff(arr, n): maxDiff = -1 for i in range(0, n): j = n - 1 while(j > i): if arr[j] > arr[i] and maxDiff < (j - i): maxDiff = j - i j -= 1 return maxDiff # driver code arr = [9, 2, 3, 4, 5, 6, 7, 8, 18, 0] n = len(arr) maxDiff = maxIndexDiff(arr, n) print(maxDiff) # This article is contributed by Smitha Dinesh Semwal
C#
// C# program to find the maximum
// j – i such that arr[j] > arr[i]
using System;
class GFG {
// For a given array arr[], returns
// the maximum j-i such that arr[j] > arr[i]
static int maxIndexDiff(int[] arr, int n)
{
int maxDiff = -1;
int i, j;
for (i = 0; i < n; ++i) {
for (j = n - 1; j > i; --j) {
if (arr[j] > arr[i] && maxDiff < (j - i))
maxDiff = j - i;
}
}
return maxDiff;
}
// Driver program
public static void Main()
{
int[] arr = { 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 };
int n = arr.Length;
int maxDiff = maxIndexDiff(arr, n);
Console.Write(maxDiff);
}
}
// This Code is Contributed by Sam007
PHP
<?php
// PHP program to find the maximum
// j – i such that arr[j] > arr[i]
// For a given array arr[], returns
// the maximum j – i such that
// arr[j] > arr[i]
function maxIndexDiff($arr, $n)
{
$maxDiff = -1;
for ($i = 0; $i < $n; ++$i)
{
for ($j = $n - 1; $j > $i; --$j)
{
if($arr[$j] > $arr[$i] &&
$maxDiff < ($j - $i))
$maxDiff = $j - $i;
}
}
return $maxDiff;
}
// Driver Code
$arr = array(9, 2, 3, 4, 5,
6, 7, 8, 18, 0);
$n = count($arr);
$maxDiff = maxIndexDiff($arr, $n);
echo $maxDiff ;
// This code is contributed by Sam007
?>
Javascript
<script>
// JavaScript program for the above approach
/* For a given array arr[],
returns the maximum j – i such
that arr[j] > arr[i] */
function maxIndexDiff(arr, n)
{
let maxDiff = -1;
let i, j;
for (i = 0; i < n; ++i)
{
for (j = n - 1; j > i; --j)
{
if (arr[j] > arr[i] && maxDiff < (j - i))
maxDiff = j - i;
}
}
return maxDiff;
}
// Driver code
let arr = [ 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 ];
let n = arr.length;
let maxDiff = maxIndexDiff(arr, n);
document.write(maxDiff);
// This code is contributed by Manoj.
</script>
Producción
8
Tiempo Complejidad: O(n 2 )
Espacio Auxiliar: O(1)
Método 2: Improvisando el Algoritmo de Fuerza Bruta y buscando BUD, es decir, cuellos de botella, trabajos innecesarios y duplicados. Una observación rápida en realidad muestra que hemos estado buscando encontrar el primer elemento más grande que atraviese desde el final de la array hasta el índice actual. Podemos ver que estamos tratando de encontrar el primer elemento mayor una y otra vez para cada elemento de la array. Digamos que tenemos una array con nosotros, por ejemplo [1, 5, 12, 4, 9] ahora sabemos que 9 es el elemento que es mayor que 1, 5 y 4, pero ¿por qué necesitamos encontrar eso una y otra vez? . De hecho, podemos realizar un seguimiento del número máximo que se mueve desde el final hasta el comienzo de la array. El enfoque nos ayudará a entender mejor y también esta improvisación es genial para hacer una entrevista.
Acercarse :
- Recorra la array desde el final y mantenga un registro del número máximo a la derecha del índice actual, incluido uno mismo
- Ahora tenemos una array decreciente monótona, y sabemos que podemos usar la búsqueda binaria para encontrar el índice del elemento mayor más a la derecha
- Ahora solo usaremos la búsqueda binaria para cada uno de los elementos en la array y almacenaremos la diferencia máxima de los índices y eso es todo.
C++
/* For a given array arr[],
calculates the maximum j – i
such that arr[j] > arr[i] */
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<long long int> v{
34, 8, 10, 3, 2, 80, 30, 33, 1
};
int n = v.size();
vector<long long int> maxFromEnd(n + 1, INT_MIN);
// create an array maxfromEnd
for (int i = v.size() - 1; i >= 0; i--) {
maxFromEnd[i] = max(maxFromEnd[i + 1], v[i]);
}
int result = 0;
for (int i = 0; i < v.size(); i++) {
int low = i + 1, high = v.size() - 1, ans = i;
while (low <= high) {
int mid = (low + high) / 2;
if (v[i] <= maxFromEnd[mid]) {
// We store this as current answer and look
// for further larger number to the right
// side
ans = max(ans, mid);
low = mid + 1;
}
else {
high = mid - 1;
}
}
// keeping a track of the
// maximum difference in indices
result = max(result, ans - i);
}
cout << result << endl;
}
C
/* C program to implement
the above approach */
/* For a given array arr[],
calculates the maximum j – i
such that arr[j] > arr[i] */
#include <limits.h>
#include <stdio.h>
/* Function for maximum of
two numbers in C */
int max(int num1, int num2)
{
return (num1 > num2 ) ? num1 : num2;
}
int main()
{
int v[] = { 34, 8, 10, 3, 2, 80, 30, 33, 1 };
int n = sizeof(v) / sizeof(v[0]);
int maxFromEnd[n+1];
for (int i = 0; i < n+1; i++) {
maxFromEnd[i] = INT_MIN;
}
// create an array maxfromEnd
for (int i = n - 1; i >= 0; i--) {
maxFromEnd[i] = max(maxFromEnd[i + 1], v[i]);
}
int result = 0;
for (int i = 0; i < n; i++) {
int low = i + 1, high = n - 1, ans = i;
while (low <= high) {
int mid = (low + high) / 2;
if (v[i] <= maxFromEnd[mid]) {
// We store this as current answer and look
// for further larger number to the right
// side
ans = max(ans, mid);
low = mid + 1;
}
else {
high = mid - 1;
}
}
// keeping a track of the
// maximum difference in indices
result = max(result, ans - i);
}
printf("\n %d", result);
}
/* This code is contributed by Pushpesh Raj */
Java
// Java program to implement
// the above approach
// For a given array arr[],
// calculates the maximum j – i
// such that arr[j] > arr[i]
import java.util.*;
class GFG{
public static void main(String[] args)
{
int []v = {34, 8, 10, 3, 2,
80, 30, 33, 1};
int n = v.length;
int []maxFromEnd = new int[n + 1];
Arrays.fill(maxFromEnd, Integer.MIN_VALUE);
// Create an array maxfromEnd
for (int i = v.length - 1; i >= 0; i--)
{
maxFromEnd[i] = Math.max(maxFromEnd[i + 1],
v[i]);
}
int result = 0;
for (int i = 0; i < v.length; i++)
{
int low = i + 1, high = v.length - 1,
ans = i;
while (low <= high)
{
int mid = (low + high) / 2;
if (v[i] <= maxFromEnd[mid])
{
// We store this as current
// answer and look for further
// larger number to the right side
ans = Math.max(ans, mid);
low = mid + 1;
}
else
{
high = mid - 1;
}
}
// Keeping a track of the
// maximum difference in indices
result = Math.max(result, ans - i);
}
System.out.print(result + "\n");
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program to implement # the above approach # For a given array arr, # calculates the maximum j – i # such that arr[j] > arr[i] # Driver code if __name__ == '__main__': v = [34, 8, 10, 3, 2, 80, 30, 33, 1]; n = len(v); maxFromEnd = [-38749432] * (n + 1); # Create an array maxfromEnd for i in range(n - 1, 0, -1): maxFromEnd[i] = max(maxFromEnd[i + 1], v[i]); result = 0; for i in range(0, n): low = i + 1; high = n - 1; ans = i; while (low <= high): mid = int((low + high) / 2); if (v[i] <= maxFromEnd[mid]): # We store this as current # answer and look for further # larger number to the right side ans = max(ans, mid); low = mid + 1; else: high = mid - 1; # Keeping a track of the # maximum difference in indices result = max(result, ans - i); print(result, end = ""); # This code is contributed by Rajput-Ji
C#
// C# program to implement
// the above approach
// For a given array []arr,
// calculates the maximum j – i
// such that arr[j] > arr[i]
using System;
class GFG{
public static void Main(String[] args)
{
int []v = {34, 8, 10, 3, 2,
80, 30, 33, 1};
int n = v.Length;
int []maxFromEnd = new int[n + 1];
for (int i = 0;
i < maxFromEnd.Length; i++)
maxFromEnd[i] = int.MinValue;
// Create an array maxfromEnd
for (int i = v.Length - 1;
i >= 0; i--)
{
maxFromEnd[i] = Math.Max(maxFromEnd[i + 1],
v[i]);
}
int result = 0;
for (int i = 0; i < v.Length; i++)
{
int low = i + 1,
high = v.Length - 1,
ans = i;
while (low <= high)
{
int mid = (low + high) / 2;
if (v[i] <= maxFromEnd[mid])
{
// We store this as current
// answer and look for further
// larger number to the right side
ans = Math.Max(ans, mid);
low = mid + 1;
}
else
{
high = mid - 1;
}
}
// Keeping a track of the
// maximum difference in indices
result = Math.Max(result, ans - i);
}
Console.Write(result + "\n");
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program to implement
// the above approach
// For a given array []arr,
// calculates the maximum j – i
// such that arr[j] > arr[i]
let v = [34, 8, 10, 3, 2, 80, 30, 33, 1];
let n = v.length;
let maxFromEnd = new Array(n + 1);
for (let i = 0; i < maxFromEnd.length; i++)
maxFromEnd[i] = Number.MIN_VALUE;
// Create an array maxfromEnd
for (let i = v.length - 1; i >= 0; i--)
{
maxFromEnd[i] = Math.max(maxFromEnd[i + 1], v[i]);
}
let result = 0;
for (let i = 0; i < v.length; i++)
{
let low = i + 1, high = v.length - 1, ans = i;
while (low <= high)
{
let mid = parseInt((low + high) / 2, 10);
if (v[i] <= maxFromEnd[mid])
{
// We store this as current
// answer and look for further
// larger number to the right side
ans = Math.max(ans, mid);
low = mid + 1;
}
else
{
high = mid - 1;
}
}
// Keeping a track of the
// maximum difference in indices
result = Math.max(result, ans - i);
}
document.write(result);
</script>
Producción
6
Complejidad de tiempo: O(N*log(N))
Complejidad de espacio: O(N)
Método 3 O(nLgn): Use hashing y sorting para resolver este problema en menos de una complejidad cuadrática después de tener especial cuidado con los duplicados.
Acercarse :
- Recorra la array y almacene el índice de cada elemento en una lista (para manejar duplicados).
- Ordenar la array.
- Ahora recorra la array y realice un seguimiento de la diferencia máxima de i y j.
- Para j considere el último índice de la lista de posibles índices del elemento y para i considere el primer índice de la lista. (Como el índice se anexó en orden ascendente).
- Siga actualizando la diferencia máxima hasta el final de la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of
// the hashmap approach
#include <bits/stdc++.h>
using namespace std;
// Function to find maximum
// index difference
int maxIndexDiff(vector<int>& arr, int n)
{
// Initialise unordered_map
unordered_map<int, vector<int> > hashmap;
// Iterate from 0 to n - 1
for (int i = 0; i < n; i++) {
hashmap[arr[i]].push_back(i);
}
// Sort arr
sort(arr.begin(), arr.end());
int maxDiff = INT_MIN;
int temp = n;
// Iterate from 0 to n - 1
for (int i = 0; i < n; i++) {
if (temp > hashmap[arr[i]][0]) {
temp = hashmap[arr[i]][0];
}
maxDiff = max(
maxDiff,
hashmap[arr[i]][hashmap[arr[i]].size() - 1]
- temp);
}
return maxDiff;
}
// Driver Code
int main()
{
int n = 9;
vector<int> arr{ 34, 8, 10, 3, 2, 80, 30, 33, 1 };
// Function Call
int ans = maxIndexDiff(arr, n);
cout << "The maxIndexDiff is : " << ans << endl;
return 1;
}
Java
// Java implementation of
// the hashmap approach
import java.io.*;
import java.util.*;
class GFG{
// Function to find maximum
// index difference
static int maxIndexDiff(ArrayList<Integer> arr, int n)
{
// Initialise unordered_map
Map<Integer,
ArrayList<Integer>> hashmap = new HashMap<Integer,
ArrayList<Integer>>();
// Iterate from 0 to n - 1
for(int i = 0; i < n; i++)
{
if(hashmap.containsKey(arr.get(i)))
{
hashmap.get(arr.get(i)).add(i);
}
else
{
hashmap.put(arr.get(i), new ArrayList<Integer>());
hashmap.get(arr.get(i)).add(i);
}
}
// Sort arr
Collections.sort(arr);
int maxDiff = Integer.MIN_VALUE;
int temp = n;
// Iterate from 0 to n - 1
for(int i = 0; i < n; i++)
{
if (temp > hashmap.get(arr.get(i)).get(0))
{
temp = hashmap.get(arr.get(i)).get(0);
}
maxDiff = Math.max(maxDiff,
hashmap.get(arr.get(i)).get(
hashmap.get(arr.get(i)).size() - 1) - temp);
}
return maxDiff;
}
// Driver Code
public static void main(String[] args)
{
int n = 9;
ArrayList<Integer> arr = new ArrayList<Integer>(
Arrays.asList(34, 8, 10, 3, 2, 80, 30, 33, 1));
// Function Call
int ans = maxIndexDiff(arr, n);
System.out.println("The maxIndexDiff is : " + ans);
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 implementation of the above approach n = 9 a = [34, 8, 10, 3, 2, 80, 30, 33, 1] # To store the index of an element. index = dict() for i in range(n): if a[i] in index: # append to list (for duplicates) index[a[i]].append(i) else: # if first occurrence index[a[i]] = [i] # sort the input array a.sort() maxDiff = 0 # Temporary variable to keep track of minimum i temp = n for i in range(n): if temp > index[a[i]][0]: temp = index[a[i]][0] maxDiff = max(maxDiff, index[a[i]][-1]-temp) print(maxDiff)
C#
// C# implementation of
// the hashmap approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to find maximum
// index difference
static int maxIndexDiff(List<int> arr, int n)
{
Dictionary<int,List<int>> hashmap = new Dictionary<int,List<int>>();
// Iterate from 0 to n - 1
for(int i = 0; i < n; i++)
{
if(hashmap.ContainsKey(arr[i]))
{
hashmap[arr[i]].Add(i);
}
else
{
hashmap.Add(arr[i], new List<int>());
hashmap[arr[i]].Add(i);
}
}
// Sort arr
arr.Sort();
int maxDiff = -1;
int temp = n;
// Iterate from 0 to n - 1
for(int i = 0; i < n; i++)
{
if(temp > hashmap[arr[i]][0] )
{
temp = hashmap[arr[i]][0];
}
maxDiff = Math.Max(maxDiff,hashmap[arr[i]][hashmap[arr[i]].Count - 1]- temp);
}
return maxDiff;
}
// Driver Code
static public void Main (){
int n = 9;
List<int> arr = new List<int>();
arr.Add(34);
arr.Add(8);
arr.Add(10);
arr.Add(3);
arr.Add(2);
arr.Add(80);
arr.Add(30);
arr.Add(33);
arr.Add(1);
// Function Call
int ans = maxIndexDiff(arr, n);
Console.WriteLine("The maxIndexDiff is : " + ans );
}
}
// This code is contributed by rag2127.
Javascript
<script>
// JavaScript implementation of
// the hashmap approach
// Function to find maximum
// index difference
function maxIndexDiff(arr,n)
{
// Initialise map in JavaScript
let hashmap = new Map()
// Iterate from 0 to n - 1
for (let i = 0; i < n; i++) {
hashmap[arr[i]] = hashmap[arr[i]] || []
hashmap[arr[i]].push(i)
}
// Sort arr
arr.sort((a,b)=> (a - b))
let maxDiff = 0
let temp = n
// Iterate from 0 to n - 1
for (let i = 0; i < n; i++) {
if (temp > hashmap[arr[i]][0]) {
temp = hashmap[arr[i]][0]
}
maxDiff = Math.max( maxDiff,hashmap[arr[i]][hashmap[arr[i]].length - 1]- temp )
}
return maxDiff
}
// Driver Code
let n = 9
const arr = [ 34, 8, 10, 3, 2, 80, 30, 33, 1 ]
// Function Call
let ans = maxIndexDiff(arr, n)
document.write(`The maxIndexDiff is : ${ans}`)
// This code is contributed by shinjanpatra
</script>
Producción
The maxIndexDiff is : 6
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N)
Método 4 (eficiente):Para resolver este problema, necesitamos obtener dos índices óptimos de arr[]: el índice izquierdo i y el índice derecho j. Para un elemento arr[i], no necesitamos considerar arr[i] para el índice izquierdo si hay un elemento más pequeño que arr[i] en el lado izquierdo de arr[i]. De manera similar, si hay un elemento mayor en el lado derecho de arr[j], entonces no necesitamos considerar este j para el índice derecho. Entonces construimos dos arreglos auxiliares LMin[] y RMax[] tales que LMin[i] contiene el elemento más pequeño en el lado izquierdo de arr[i] incluyendo arr[i], y RMax[j] contiene el elemento más grande en el lado derecho de arr[j] incluyendo arr[j]. Después de construir estos dos arreglos auxiliares, recorremos ambos arreglos de izquierda a derecha. Al atravesar LMin[] y RMax[] si vemos que LMin[i] es mayor que RMax[j], entonces debemos avanzar en LMin[] (o hacer i++) porque todos los elementos a la izquierda de LMin[i] son mayores o iguales que LMin[i]. De lo contrario, debemos avanzar en RMax[j] para buscar un valor mayor de j – i.
Gracias a celicom por sugerir el algoritmo para este método.
Ejemplo de trabajo:
Consideremos cualquier ejemplo [7 3 1 8 9 10 4 5 6]
¿Qué es maxRight?
Llenar desde el lado derecho 6 es el primer elemento ahora 6> 5, así que nuevamente llenamos 6 hasta llegar a 10> 6:
[10 10 10 10 10 10 6 6 6] esto es maxR
[7 3 1 1 1 1 1 1 1 ] esto es minL
¡ahora vemos cómo llegar a la respuesta de estos a y su prueba!
comparemos los primeros elementos de las arrays ahora vemos 10> 7,
ahora aumentamos maxR en 1 hasta que sea menor que 7, es decir, en el índice 5
por lo tanto, la respuesta hasta ahora es. 5-0 = 5
ahora aumentaremos minL, obtenemos 3, que es menor que 6, por lo que aumentamos maxR hasta que alcanza el último índice y la respuesta se convierte en 8-1 = 7
entonces vemos cómo estamos obteniendo la respuesta correcta.
Como necesitamos la diferencia máxima j – i tal que A[i]<= A[j], por lo tanto, no necesitamos considerar el elemento después del índice j y el elemento antes del índice i.
en la sugerencia anterior, haga 2 arrays,
Primero, almacenará el elemento más pequeño antes del elemento
En segundo lugar, almacenará el elemento más grande que ocurra después del elemento
Atraviese la segunda array, hasta que el elemento de la segunda array sea mayor o igual que la primera array, y almacene la diferencia de índice. Y si se vuelve más pequeño, atraviesa la primera array hasta que vuelva a ser más grande.
Y almacene la diferencia máxima de esta diferencia de índice.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
/* For a given array arr[],
returns the maximum j – i such that
arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
int maxDiff;
int i, j;
int* LMin = new int[(sizeof(int) * n)];
int* RMax = new int[(sizeof(int) * n)];
/* Construct LMin[] such that
LMin[i] stores the minimum value
from (arr[0], arr[1], ... arr[i]) */
LMin[0] = arr[0];
for (i = 1; i < n; ++i)
LMin[i] = min(arr[i], LMin[i - 1]);
/* Construct RMax[] such that
RMax[j] stores the maximum value from
(arr[j], arr[j+1], ..arr[n-1]) */
RMax[n - 1] = arr[n - 1];
for (j = n - 2; j >= 0; --j)
RMax[j] = max(arr[j], RMax[j + 1]);
/* Traverse both arrays from left to right
to find optimum j - i. This process is similar to
merge() of MergeSort */
i = 0, j = 0, maxDiff = -1;
while (j < n && i < n) {
if (LMin[i] <= RMax[j]) {
maxDiff = max(maxDiff, j - i);
j = j + 1;
}
else
i = i + 1;
}
return maxDiff;
}
// Driver Code
int main()
{
int arr[] = { 9, 2, 3, 4, 5,
6, 7, 8, 18, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
int maxDiff = maxIndexDiff(arr, n);
cout << maxDiff;
return 0;
}
// This code is contributed by rathbhupendra
C
#include <stdio.h>
/* Utility Functions to get max and minimum of two integers */
int max(int x, int y)
{
return x > y ? x : y;
}
int min(int x, int y)
{
return x < y ? x : y;
}
/* For a given array arr[], returns the maximum j – i such that
arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
int maxDiff;
int i, j;
int* LMin = (int*)malloc(sizeof(int) * n);
int* RMax = (int*)malloc(sizeof(int) * n);
/* Construct LMin[] such that LMin[i] stores the minimum value
from (arr[0], arr[1], ... arr[i]) */
LMin[0] = arr[0];
for (i = 1; i < n; ++i)
LMin[i] = min(arr[i], LMin[i - 1]);
/* Construct RMax[] such that RMax[j] stores the maximum value
from (arr[j], arr[j+1], ..arr[n-1]) */
RMax[n - 1] = arr[n - 1];
for (j = n - 2; j >= 0; --j)
RMax[j] = max(arr[j], RMax[j + 1]);
/* Traverse both arrays from left to right to find optimum j - i
This process is similar to merge() of MergeSort */
i = 0, j = 0, maxDiff = -1;
while (j < n && i < n) {
if (LMin[i] <= RMax[j]) {
maxDiff = max(maxDiff, j - i);
j = j + 1;
}
else
i = i + 1;
}
return maxDiff;
}
/* Driver program to test above functions */
int main()
{
int arr[] = { 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
int maxDiff = maxIndexDiff(arr, n);
printf("\n %d", maxDiff);
getchar();
return 0;
}
Java
class FindMaximum {
/* Utility Functions to get max and minimum of two integers */
int max(int x, int y)
{
return x > y ? x : y;
}
int min(int x, int y)
{
return x < y ? x : y;
}
/* For a given array arr[], returns the maximum j-i such that
arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
int maxDiff;
int i, j;
int RMax[] = new int[n];
int LMin[] = new int[n];
/* Construct LMin[] such that LMin[i] stores the minimum value
from (arr[0], arr[1], ... arr[i]) */
LMin[0] = arr[0];
for (i = 1; i < n; ++i)
LMin[i] = min(arr[i], LMin[i - 1]);
/* Construct RMax[] such that RMax[j] stores the maximum value
from (arr[j], arr[j+1], ..arr[n-1]) */
RMax[n - 1] = arr[n - 1];
for (j = n - 2; j >= 0; --j)
RMax[j] = max(arr[j], RMax[j + 1]);
/* Traverse both arrays from left to right to find optimum j - i
This process is similar to merge() of MergeSort */
i = 0;
j = 0;
maxDiff = -1;
while (j < n && i < n) {
if (LMin[i] <= RMax[j]) {
maxDiff = max(maxDiff, j - i);
j = j + 1;
}
else
i = i + 1;
}
return maxDiff;
}
/* Driver program to test the above functions */
public static void main(String[] args)
{
FindMaximum max = new FindMaximum();
int arr[] = { 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 };
int n = arr.length;
int maxDiff = max.maxIndexDiff(arr, n);
System.out.println(maxDiff);
}
}
Python3
# Utility Functions to get max # and minimum of two integers def max(a, b): if(a > b): return a else: return b def min(a, b): if(a < b): return a else: return b # For a given array arr[], # returns the maximum j - i # such that arr[j] > arr[i] def maxIndexDiff(arr, n): maxDiff = 0; LMin = [0] * n RMax = [0] * n # Construct LMin[] such that # LMin[i] stores the minimum # value from (arr[0], arr[1], # ... arr[i]) LMin[0] = arr[0] for i in range(1, n): LMin[i] = min(arr[i], LMin[i - 1]) # Construct RMax[] such that # RMax[j] stores the maximum # value from (arr[j], arr[j + 1], # ..arr[n-1]) RMax[n - 1] = arr[n - 1] for j in range(n - 2, -1, -1): RMax[j] = max(arr[j], RMax[j + 1]); # Traverse both arrays from left # to right to find optimum j - i # This process is similar to # merge() of MergeSort i, j = 0, 0 maxDiff = -1 while (j < n and i < n): if (LMin[i] <= RMax[j]): maxDiff = max(maxDiff, j - i) j = j + 1 else: i = i + 1 return maxDiff # Driver Code if(__name__ == '__main__'): arr = [9, 2, 3, 4, 5, 6, 7, 8, 18, 0] n = len(arr) maxDiff = maxIndexDiff(arr, n) print (maxDiff) # This code is contributed # by gautam karakoti
C#
// C# program to find the maximum
// j – i such that arr[j] > arr[i]
using System;
class GFG {
// Utility Functions to get max
// and minimum of two integers
static int max(int x, int y)
{
return x > y ? x : y;
}
static int min(int x, int y)
{
return x < y ? x : y;
}
// For a given array arr[], returns
// the maximum j-i such thatarr[j] > arr[i]
static int maxIndexDiff(int[] arr, int n)
{
int maxDiff;
int i, j;
int[] RMax = new int[n];
int[] LMin = new int[n];
// Construct LMin[] such that LMin[i]
// stores the minimum value
// from (arr[0], arr[1], ... arr[i])
LMin[0] = arr[0];
for (i = 1; i < n; ++i)
LMin[i] = min(arr[i], LMin[i - 1]);
// Construct RMax[] such that
// RMax[j] stores the maximum value
// from (arr[j], arr[j+1], ..arr[n-1])
RMax[n - 1] = arr[n - 1];
for (j = n - 2; j >= 0; --j)
RMax[j] = max(arr[j], RMax[j + 1]);
// Traverse both arrays from left
// to right to find optimum j - i
// This process is similar to merge()
// of MergeSort
i = 0;
j = 0;
maxDiff = -1;
while (j < n && i < n) {
if (LMin[i] <= RMax[j]) {
maxDiff = max(maxDiff, j - i);
j = j + 1;
}
else
i = i + 1;
}
return maxDiff;
}
// Driver program
public static void Main()
{
int[] arr = { 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 };
int n = arr.Length;
int maxDiff = maxIndexDiff(arr, n);
Console.Write(maxDiff);
}
}
// This Code is Contributed by Sam007
PHP
<?php
// PHP program to find the maximum
// j – i such that arr[j] > arr[i]
// For a given array arr[],
// returns the maximum j - i
// such that arr[j] > arr[i]
function maxIndexDiff($arr, $n)
{
$maxDiff = 0;
$LMin = array_fill(0, $n, NULL);
$RMax = array_fill(0, $n, NULL);
// Construct LMin[] such that
// LMin[i] stores the minimum
// value from (arr[0], arr[1],
// ... arr[i])
$LMin[0] = $arr[0];
for($i = 1; $i < $n; $i++)
$LMin[$i] = min($arr[$i],
$LMin[$i - 1]);
// Construct RMax[] such that
// RMax[j] stores the maximum
// value from (arr[j], arr[j+1],
// ..arr[n-1])
$RMax[$n - 1] = $arr[$n - 1];
for($j = $n - 2; $j >= 0; $j--)
$RMax[$j] = max($arr[$j],
$RMax[$j + 1]);
// Traverse both arrays from left
// to right to find optimum j - i
// This process is similar to
// merge() of MergeSort
$i = 0;
$j = 0;
$maxDiff = -1;
while ($j < $n && $i < $n)
if ($LMin[$i] <= $RMax[$j])
{
$maxDiff = max($maxDiff, $j - $i);
$j = $j + 1;
}
else
$i = $i + 1;
return $maxDiff;
}
// Driver Code
$arr = array(9, 2, 3, 4, 5,
6, 7, 8, 18, 0);
$n = sizeof($arr);
$maxDiff = maxIndexDiff($arr, $n);
echo $maxDiff;
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript program to find the maximum
// j – i such that arr[j] > arr[i]
// Utility Functions to get max
// and minimum of two integers
function max(x, y)
{
return x > y ? x : y;
}
function min(x, y)
{
return x < y ? x : y;
}
// For a given array arr[], returns
// the maximum j-i such thatarr[j] > arr[i]
function maxIndexDiff(arr, n)
{
let maxDiff;
let i, j;
let RMax = new Array(n);
let LMin = new Array(n);
// Construct LMin[] such that LMin[i]
// stores the minimum value
// from (arr[0], arr[1], ... arr[i])
LMin[0] = arr[0];
for (i = 1; i < n; ++i)
LMin[i] = min(arr[i], LMin[i - 1]);
// Construct RMax[] such that
// RMax[j] stores the maximum value
// from (arr[j], arr[j+1], ..arr[n-1])
RMax[n - 1] = arr[n - 1];
for (j = n - 2; j >= 0; --j)
RMax[j] = max(arr[j], RMax[j + 1]);
// Traverse both arrays from left
// to right to find optimum j - i
// This process is similar to merge()
// of MergeSort
i = 0;
j = 0;
maxDiff = -1;
while (j < n && i < n) {
if (LMin[i] <= RMax[j]) {
maxDiff = max(maxDiff, j - i);
j = j + 1;
}
else
i = i + 1;
}
return maxDiff;
}
let arr = [ 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 ];
let n = arr.length;
let maxDiff = maxIndexDiff(arr, n);
document.write(maxDiff);
</script>
Producción
8
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Escriba comentarios si encuentra que los códigos/algoritmos anteriores son incorrectos o encuentra otras formas de resolver el mismo problema.
Otro enfoque: (solo usando una array adicional):Consideramos un arreglo auxiliar: rightMax[] , tal que, rightMax[i] = elemento máximo del subarreglo arr[i…(n-1)], el elemento más grande o igual después del elemento arr[i] Supongamos (arr[i ], arr[jLast] ) es un par, tal que arr[jLast] es el último elemento mayor o igual que arr[i]. Para los pares que terminan en arr[jÚltimo]: ( arr[k], arr[jÚltimo] ) para todo k = (i+1) a jÚltimo no necesitamos considerar (jÚltimo – k) porque (jÚltimo – i ) > (jÚltimo – k) para todas las k. Así que podemos saltarnos esos pares. Recorriendo de izquierda a derecha ambas arrays: arr[] y rightMax[] , cuando encontramos por primera vez rightMax[j] < arr[i[ , sabemos que jLast = j-1, y podemos omitir los pares (arr[k ], arr[jÚltimo]) para todos los k = (i+1) a jÚltimo. Y también rightMax[] es una secuencia no creciente, por lo que todos los elementos en el lado derecho de rightMax[j] son menores o iguales que rightMax[j].
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
/* For a given array arr[],
returns the maximum j – i such that
arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
int rightMax[n];
rightMax[n-1]= arr[n-1];
for(int i = n-2; i>=0; i--)
rightMax[i] = max(rightMax[i+1] , arr[i]);
//rightMax[i] = max{ arr[i...(n-1] }
int maxDist = INT_MIN;
int i = 0, j = 0;
while(i<n && j<n)
{
if(rightMax[j] >= arr[i])
{
maxDist = max( maxDist, j-i );
j++;
}
else // if(rightMax[j] < leftMin[i])
i++;
}
return maxDist;
}
// Driver Code
int main()
{
int arr[] = { 34,8,10,3,2,80,30,33,1};
int n = sizeof(arr) / sizeof(arr[0]);
int maxDiff = maxIndexDiff(arr, n);
cout << maxDiff;
return 0;
}
// This code is contributed by Sourashis Mondal
Java
import java.util.*;
class GFG{
/* For a given array arr[],
returns the maximum j – i such that
arr[j] > arr[i] */
static int maxIndexDiff(int arr[], int n)
{
int []rightMax = new int[n];
rightMax[n-1]= arr[n-1];
for(int i = n-2; i>=0; i--)
rightMax[i] = Math.max(rightMax[i+1] , arr[i]);
// rightMax[i] = max{ arr[i...(n-1] }
int maxDist = Integer.MIN_VALUE;
int i = 0, j = 0;
while(i < n && j < n)
{
if(rightMax[j] >= arr[i])
{
maxDist = Math.max( maxDist, j-i );
j++;
}
else // if(rightMax[j] < leftMin[i])
i++;
}
return maxDist;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {34, 8, 10, 3, 2, 80, 30, 33, 1};
int n = arr.length;
int maxDiff = maxIndexDiff(arr, n);
System.out.print(maxDiff);
}
}
// This code is contributed by Rajput-Ji
Python3
# For a given array arr[], returns the # maximum j – i such that arr[j] > arr[i] def maxIndexDiff(arr, n): rightMax = [0] * n rightMax[n - 1] = arr[n - 1] for i in range(n - 2, -1, -1): rightMax[i] = max(rightMax[i + 1], arr[i]) # rightMax[i] = max arr[i...(n-1] maxDist = -2**31 i = 0 j = 0 while (i < n and j < n): if (rightMax[j] >= arr[i]): maxDist = max(maxDist, j - i) j += 1 else: # if(rightMax[j] < leftMin[i]) i += 1 return maxDist # Driver Code arr = [ 34, 8, 10, 3, 2, 80, 30, 33, 1 ] n = len(arr) maxDiff = maxIndexDiff(arr, n) print(maxDiff) # This code is contributed by Shubham Singh
C#
/* For a given array arr[],
returns the maximum j – i such that
arr[j] > arr[i] */
using System;
public class GFG
{
static int maxIndexDiff(int[] arr, int n)
{
int []rightMax = new int[n];
rightMax[n - 1] = arr[n - 1];
int i = 0, j = 0;
for(i = n - 2; i >= 0; i--)
rightMax[i] = Math.Max(rightMax[i+1] , arr[i]);
// rightMax[i] = max{ arr[i...(n-1] }
int maxDist = Int32.MinValue;
i = 0;
while(i < n && j < n)
{
if(rightMax[j] >= arr[i])
{
maxDist = Math.Max( maxDist, j - i);
j++;
}
else // if(rightMax[j] < leftMin[i])
i++;
}
return maxDist;
}
// Driver Code
public static void Main()
{
int[] arr = {34, 8, 10, 3, 2, 80, 30, 33, 1};
int n = arr.Length;
int maxDiff = maxIndexDiff(arr, n);
Console.Write(maxDiff);
}
}
// This code is contributed by Shubham Singh
Javascript
<script>
/* For a given array arr[],
returns the maximum j – i such that
arr[j] > arr[i] */
function maxIndexDiff(arr, n)
{
var rightMax = new Array(n).fill(0);;
rightMax[n - 1] = arr[n - 1];
for(var i = n - 2; i >= 0; i--){
rightMax[i] = Math.max(rightMax[i+1] , arr[i]);
}
// rightMax[i] = max{ arr[i...(n-1] }
var maxDist = Number.MIN_VALUE;
var i = 0;
var j = 0;
while(i < n && j < n)
{
if(rightMax[j] >= arr[i])
{
maxDist = Math.max( maxDist, j-i );
j++;
}
else // if(rightMax[j] < leftMin[i])
{ i++;
}
}
return maxDist;
}
// Driver Code
var arr = [ 34,8,10,3,2,80,30,33,1];
var n = arr.length;
var maxDiff = maxIndexDiff(arr, n);
document.write(maxDiff);
// This code is contributed by Shubham Singh
</script>
Producción
6
Complejidad temporal: O(n), Como los punteros i y j atraviesan como máximo n elementos, complejidad temporal = O(n) + O(n) = O(n)
Espacio auxiliar: O(n)
Usando leftMin[]: También podemos hacer esto usando solo el arreglo leftMin[], donde leftMin[i] = elemento mínimo del subarreglo arr[0…i]
C++
#include <bits/stdc++.h>
using namespace std;
/* For a given array arr[],
returns the maximum j – i such that
arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
int leftMin[n] ;
leftMin[0] = arr[0];
for(int i = 1 ; i<n; i++)
leftMin[i] = min(leftMin[i-1], arr[i]);
//leftMin[i] = min{ arr[0...i] }
int maxDist = INT_MIN;
int i = n-1, j = n-1;
while(i>=0 && j>=0)
{
if(arr[j] >= leftMin[i])
{
maxDist = max(maxDist, j-i);
i--;
}
else
j--;
}
return maxDist;
}
// Driver Code
int main()
{
int arr[] = { 34,8,10,3,2,80,30,33,1};
int n = sizeof(arr) / sizeof(arr[0]);
int maxDiff = maxIndexDiff(arr, n);
cout << maxDiff;
return 0;
}
// This code is contributed by Sourashis Mondal
Java
import java.util.*;
class GFG
{
/* For a given array arr[],
returns the maximum j – i such that
arr[j] > arr[i] */
static int maxIndexDiff(int arr[], int n)
{
int []leftMin = new int[n];
leftMin[0] = arr[0];
for(int i = 1; i < n; i++)
leftMin[i] = Math.min(leftMin[i - 1] , arr[i]);
// leftMin[i] = min{ arr[i...(n-1] }
int maxDist = Integer.MIN_VALUE;
int i = n - 1, j = n - 1;
while(i >= 0 && j >= 0)
{
if(arr[j] >= leftMin[i])
{
maxDist = Math.max( maxDist, j - i );
i--;
}
else
j--;
}
return maxDist;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {34, 8, 10, 3, 2, 80, 30, 33, 1};
int n = arr.length;
int maxDiff = maxIndexDiff(arr, n);
System.out.print(maxDiff);
}
}
// This code is contributed by Shubham Singh
Python3
# For a given array arr[], # returns the maximum j – i such that # arr[j] > arr[i] */ def maxIndexDiff(arr, n): leftMin = [0]*n leftMin[0] = arr[0] for i in range(1,n): leftMin[i] = min(leftMin[i-1], arr[i]) # leftMin[i] = min arr[0...i] maxDist = - 2**32 i = n-1 j = n-1 while(i>=0 and j>=0): if(arr[j] >= leftMin[i]): maxDist = max(maxDist, j-i) i-=1 else: j-=1 return maxDist # Driver Code arr = [34,8,10,3,2,80,30,33,1] n = len(arr) maxDiff = maxIndexDiff(arr, n) print(maxDiff) # This code is contributed by Shubham Singh
C#
using System;
public class GFG{
/* For a given array arr[],
returns the maximum j – i such that
arr[j] > arr[i] */
static int maxIndexDiff(int[] arr, int n)
{
int []leftMin = new int[n];
leftMin[0] = arr[0];
int i,j;
for( i = 1; i < n; i++)
leftMin[i] = Math.Min(leftMin[i - 1] , arr[i]);
// leftMin[i] = min{ arr[i...(n-1] }
int maxDist = Int32.MinValue;
i = n - 1;
j = n - 1;
while(i >= 0 && j >= 0)
{
if(arr[j] >= leftMin[i])
{
maxDist = Math.Max( maxDist, j - i );
i--;
}
else
j--;
}
return maxDist;
}
// Driver Code
static public void Main ()
{
int[] arr = {34, 8, 10, 3, 2, 80, 30, 33, 1};
int n = arr.Length;
int maxDiff = maxIndexDiff(arr, n);
Console.Write(maxDiff);
}
}
// This code is contributed by Shubham Singh
Javascript
<script>
/* For a given array arr[],
returns the maximum j – i such that
arr[j] > arr[i] */
function maxIndexDiff(arr, n)
{
var leftMin = new Array(n).fill(0);;
leftMin[0] = arr[0];
for(var i = 1; i < n; i++){
leftMin[i] = Math.min(leftMin[i-1] , arr[i]);
}
// leftMin[i] = min{ arr[i...(n-1] }
var maxDist = Number.MIN_VALUE;
var i = n-1;
var j = n-1;
while(i >= 0 && j >= 0)
{
if(arr[j] >= leftMin[i])
{
maxDist = Math.max( maxDist, j-i );
i--;
}
else // if(rightMax[j] < leftMin[i])
{ j--;
}
}
return maxDist;
}
// Driver Code
var arr = [ 34,8,10,3,2,80,30,33,1];
var n = arr.length;
var maxDiff = maxIndexDiff(arr, n);
document.write(maxDiff);
// This code is contributed by Shubham Singh
</script>
Producción
6
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Sugiera si alguien tiene una mejor solución que sea más eficiente en términos de espacio y tiempo.
Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA