Algoritmo: Obtener longitud del mayor subarreglo creciente de un arreglo

de Linux, Java y programación de Cristian

A falta de tiempo para cosas más profesionales, voy a ir poniendo los algoritmos bonitos que desarrolle en la Universidad. En este caso, la especificación del ejercicio sería: Dado un arreglo de números, determinar la longitud del subarreglo creciente más largo del arreglo.

Ejemplo

Si recibiéramos un arreglo de naturales con los siguientes elementos: 2, 6, 5, 1, 3, 4, 9, 8 el resultado sería 4, puesto que es el subarreglo más largo de elementos crecientes (es decir, la longitud del subarreglo 1, 3, 4, 9)

Solución en palabras

El algoritmo que resuelve este problema debería recorrer el arreglo e ir verificando si el elemento en la posición a la que apunta es menor al de la siguiente posición. Esto supone además que, puesto que evaluaremos el elemento de la siguiente posición, debemos recorrer el arreglo desde la posición 0 hasta n-1 (siendo n la longitud del arreglo), ya que no queremos sobrepasar la longitud del mismo. Por otro lado, para cada elemento del arreglo contaremos sus sucesores que sean mayores que él mismo y con dicho conteo podremos determinar cual es la longitud de los subarreglos crecientes.

Solución en Java

El algoritmo en Java sería este:

public class SubarregloCreciente{

	public static void main(String args[]){

		//arreglo a evaluar

		int[] arr = {5,6,4,1,2,6,7,78,6,2,3,4,5,6,7,3,6,1};

		//la longitud al menos sera 0;

		//k contador por cada recorrido

		int longitud = 1, k;

		//recorremos el arreglo

		for(int i=0; i< longitud =" k">

Descargar código fuente

Solución en Python

from array import array

#arreglo a evaluar

arr = array('d',[5,6,4,1,2,6,7,78,6,2,3,4,5,6,7,3,6,1])

#la longitud al menos sera 0;

#k contador por cada recorrido

longitud = 1

#k=0

#recorremos el arreglo

for i in range (0, len(arr)-1):

	#contamos desde el indice i cuantos

	#elementos hay en orden ascendente

	for k in range(i, len(arr)-1):

		if not arr[k] < longitud =" k">  
Descargar código fuente
 
Representación formal de la solución
 
 
Por supuesto, el algoritmo planteado es solo la aproximación más sencilla, mas no la más eficiente de todas.