Usando Java, ¿cómo encuentra la longitud de la matriz secundaria más grande donde el primer elemento de esta matriz es mayor o igual que el último elemento de esa matriz secundaria?

Gracias por A2A.
Para cada elemento inicial S en la matriz, podemos encontrar un elemento final E en la matriz donde [math] [/ math] [math] S> = E [/ math].
Considere [math] Si [/ math] y [math] Ei [/ math] como los índices de esos elementos. Necesitamos encontrar el máximo de
[matemática] (Ei – Si) [/ matemática] para todos los valores posibles de [matemática] S [/ matemática] y [matemática] E [/ matemática] (es decir, la longitud de la submatriz más larga que satisface sus restricciones)
Una solución simple de fuerza bruta sería comenzar un bucle en cada elemento de la matriz, hasta que encontremos un elemento que sea mayor que el inicio. Al hacer esto, podemos mantener un contador. Nuestra respuesta será el valor máximo del contador que podemos encontrar en todos los elementos iniciales. Esta solución tendría un bucle anidado, lo que da como resultado un límite superior de [matemáticas] [/ matemáticas] [matemáticas] O (N ^ 2) [/ matemáticas].
Jugando con algunos ejemplos de prueba, encontré otro método eficiente para resolver esta pregunta, que proporciona un límite superior de [matemáticas] [/ matemáticas] [matemáticas] O (N * lg (N)) [/ matemáticas].
El método es el siguiente,

1. Use cada elemento en la matriz para formar un par que contenga – [matemática] valor [/ matemática] del elemento y su posición [matemática] [/ matemática] [matemática] [/ matemática] en la matriz. Entonces, construimos una colección de pares
2. Por pares, clasifique la colección anterior en orden ascendente de valores. Para ordenar primero considere los valores y cuando dos elementos tienen los mismos valores, luego considere el orden descendente de los índices (explicaré a continuación por qué necesitamos hacer esto [A] )
3. Mantenga dos variables, una para [matemática] [/ matemática] [matemática] índice máximo actual [/ matemática] (Al inicio inicializado para indexar dentro del primer elemento en la colección ordenada de pares) y otra para [matemática] [/ matemática] [ matemáticas] longitud más larga [/ matemáticas] es decir, respuesta final
4. Comience un ciclo desde el segundo elemento de la colección ordenada de pares. Para cada pase,
   si [math] [/ math] [math] el índice máximo actual [/ math] es mayor que [math] [/ math] [math] index dentro del par actual [/ math], actualice la longitud más larga para ese elemento como [matemática] (índice máximo actual – índice de ese elemento + 1) [/ matemática], que es la longitud de la matriz secundaria más larga a partir de ese elemento.
   Si [matemática] [/ matemática] [matemática] índice máximo actual [/ matemática] era menor o igual a [matemática] [/ matemática] [matemática] índice dentro del par actual [/ matemática], entonces actualice el índice máximo actual para indexar dentro par actual

   Dentro de cada pasada de un ciclo, mantenemos [math] [/ math] [math] respuesta final [/ math] variable como máximo de la longitud más larga de subarreglos a partir del elemento en la pasada actual.

5. Nuestra solución será la variable [matemática] [/ matemática] [matemática] respuesta final [/ matemática]

Nota: [A] : al ordenar por valor del elemento, todos los elementos más pequeños se ubicarán en el lado izquierdo de la colección. Esto nos ayuda al indicar que cada elemento en el lado derecho de la colección derrotará a todos los elementos en el izquierdo. Entonces, para cada elemento de la derecha, tendremos un índice máximo que podemos obtener de todos los elementos de la izquierda. Esto asegura que para un elemento a la derecha, estamos seleccionando un elemento más alejado en la matriz original que es más pequeño o igual al elemento. También para los elementos que tienen el mismo valor, estamos considerando un orden descendente de índices, porque para un elemento de igual valor en la derecha, debemos proporcionar un índice máximo desde la izquierda.
Código:

• Cómo pasar las entrevistas de codificación para una pasantía en Facebook, Google, Microsoft, etc.
• ¿Cuál es la mejor manera de prepararse para una entrevista de pasante técnico en una semana?
• ¿Pasar tiempo en código abierto para gsoc hará que sea difícil concentrarse en la programación competitiva y, finalmente, en la preparación de entrevistas de programación?
• ¿Cuáles son las preguntas comunes que se hacen en las entrevistas sobre colecciones de Java?
• Dado un conjunto de n enteros distintos, ¿hay una manera fácil de calcular la suma de los productos de estos enteros tomados k (2 <k <n) a la vez?

import java.util. *;
import java.util.Comparator;

Solución de clase pública {

public static void main (String [] args) {
List list = new ArrayList ();
list.add (nuevo par (5, 1));
list.add (nuevo par (1, 2));
list.add (nuevo par (1, 3));
list.add (nuevo par (3, 4));
list.add (nuevo par (2, 5));
list.add (nuevo par (2, 6));

Collections.sort (list, new Pair ());

Entero currentMaxIndex = list.get (0) .getSecond ();
Entero finalAnswer = -1;
for (int i = 1; i <list.size (); i ++) {
Par p = list.get (i);
if (currentMaxIndex> p.getSecond ()) {
p.setLongestFromCurrent (currentMaxIndex – p.getSecond () + 1);
}
más{
currentMaxIndex = p.getSecond ();
}
finalAnswer = finalAnswer <p.getLongestFromCurrent ()?
p.getLongestFromCurrent (): finalAnswer;
}

System.out.println (“Longitud más larga de SubArray:” + finalAnswer);
}

}

La clase Par implementa Comparador {

entero privado primero;
entero privado segundo;
entero privado longestFromCurrent;

Par(){
this.first = 0;
this.second = 0;
this.longestFromCurrent = 1;
}

Par (entero primero, entero segundo) {
this.first = first;
this.second = second;
this.longestFromCurrent = 1;
}

public int compare (Par a, Par b) {
if (a.first == b.first) {
return b.second – a.second;
}
volver a.first – b.first;
}

public String toString () {
devuelve “Primero:” + this.first + “, Segundo:” + this.second + “, Longitud del subarreglo más largo de la corriente:” + this.longestFromCurrent;
}

public Integer getLongestFromCurrent () {
return longestFromCurrent;
}

public void setLongestFromCurrent (Integer longestFromCurrent) {
this.longestFromCurrent = longestFromCurrent;
}

public Integer getFirst () {
volver primero;
}

entero público getSecond () {
volver segundo;
}

}

Había implementado la Interfaz del comparador para ordenar por pares, modifiqué su método de comparación para adaptarlo a nuestra restricción → para ordenar valores iguales en índices descendentes y para valores desiguales ordenar por orden ascendente.
El método Collections.sort () es una versión modificada del tipo de combinación, que se limita a [math] O (Nlg (N)) [/ math]. Todos los demás bucles dentro del código están vinculados a [math] O (N). [/ Math]
Por lo tanto, la complejidad temporal es [matemática] O (Nlg (N) [/ matemática]).

Ejemplo de ejemplo para el código anterior:

Solución:

¡Feliz codificación!