El desafío es escribir la implementación más corta para encontrar la subsecuencia de mayor crecimiento .

Ejemplo : Sea S la secuencia 1 5 7 1 8 4 3 5 [longitud de S = 8]

• Tenemos 1 subsecuencia de longitud 0 [lo consideraremos creciente]
  
• 6 subsecuencias de longitud 1 {1,5,7,8,4,3} [todas se consideran en aumento]
  
• (7 * 8) / 2 subsecuencias de longitud 2 [pero eliminaremos los duplicados], las subsecuentes crecientes están en negro intenso.
  { 15,17 , 11, 18,14,13,57 , 51, 58 , 54,53,55,71, 78 , 74,73,75,84,83,85,43, 45,35 }
  

[tenga en cuenta que solo nos interesan las subsecuencias estrictamente crecientes]

[no puede cambiar el orden de los elementos dentro de la secuencia, por lo que no hay una subsecuencia [37] en la secuencia de ejemplo]

• Tenemos subsecuencias crecientes de longitud 4, que es 1578, pero no hay una subsecuencia de longitud 5, por lo que consideramos la longitud de la subsecuencia creciente más larga = 4.
  

Entrada :

a ₁ a ₂ ... a _N (La secuencia)

todos los números son enteros positivos menores que 10 ³
N <= 1000

Salida :

Un número entero que indica la longitud de la subsecuencia creciente más larga de la secuencia de entrada.

sample input(1)
1 2 4 2 5
sample output(1)
4

sample input(2)
1 5 7 1 8 4 3 5
sample output(2)
4

Su código debe ejecutarse de manera oportuna, pruebe su código en este caso antes de enviarlo aquí (también el enlace contiene mi solución c ++ 11 de 290 bytes)

Puede tomar la entrada de un archivo / stdin o como un parámetro de función y puede imprimir la salida en un archivo / stdout o simplemente devolver el valor si escribe una función

Tablero de puntuación

1. Dennis CJam - 22
2. Isaac Pyth - 26
3. Howard GolfScript - 35
4. orgulloso Haskeller Haskell - 56
5. Ray Python 3 - 66
6. histocrat Ruby - 67
7. DLeh C # - 92
8. YosemiteMark Clojure - 94
9. faubiguy Python 3 - 113

CJam, 22 bytes

1e3,q~{_2$<$0=(t}/$0=z

Pruébalo en línea.

Ejemplo

$ cjam subsequence.cjam <<< '[2 1]'; echo
1
$ cjam subsequence.cjam <<< '[1 9 2 4 3 5]'; echo
4

El programa imprime 57para este caso de prueba después de 0.25 segundos.

Cómo funciona

Tomé la idea general de la respuesta de @ Ray .

1e3,    " Push the array [ 0 ... 999 ] (J).        ";
q~      " Read from STDIN and evaluate.            ";
{       " For each integer (I) of the input array: ";
  _2$<  " Push [ J[0] ... J[I - 1] ] (A).          ";
  $0=(  " Compute min(A) - 1.                      ";
  t     " Update J[I] with the value on the stack. ";
}/      "                                          ";
$0=     " Compute abs(min(J)).                     ";

Pitón 3, 66

Tenga en cuenta que todos los números están en el rango [1, 999], podemos usar una matriz bpara mantener la longitud de subsecuencia más larga que termina con cada número. b[x] = dsignifica que la subsecuencia más larga que termina en xtiene longitud d. Para cada número de la entrada, actualizamos la matriz usando b[x] = max(b[:x]) + 1y luego terminamos el trabajo tomando max(b)finalmente.

La complejidad del tiempo es En) O (mn) , donde msiempre es 1000 y nes el número de elementos de entrada.

def f(a):
 b=[0]*1000
 for x in a:b[x]=max(b[:x])+1
 return max(b)

Wow, parece que ya no tiene golf :) Puedes probarlo usando stdin / stdout agregando una línea:

print(f(map(int,input().split())))

Python - 113

a=[]
for i in map(int,input().split()):
 if not a or i>a[-1]:a+=[i]
 z=0
 while a[z]<i:z+=1
 a[z]=i
print(len(a))

Pyth , 26 29 33 39

J*]0^T3Fkyw=@JkheS:J0k)eSJ

Puerto de la solución de @ ray. Pasa las pruebas oficiales. Ahora usa la entrada STDIN separada por espacios, no la función de llamada.

Ejecute de la siguiente manera:

./pyth.py -c "J*]0^T3Fkyw=@JkheS:J0k)eSJ" <<< "1 5 7 2 8 4 3 5"
4

Explicación:

J*]0^T3                 J = [0]*10^3
Fkyw                    For k in space_sep(input()):
=@Jk                    J[k]=
heS:J0k                 max(J[0:k])+1
)                       end for
eSJ                     max(J)

Tiempo ilimitado:

Pyth , 18

L?eS,ytbhyf>Thbbb0

Nota técnica: Noté un error en mi compilador Pyth mientras escribía este golf. LNo estaba funcionando. Es por eso que hay un compromiso reciente con el repositorio git anterior.

Clojure, 94 caracteres

Usando el enfoque de @ Ray de actualizar los resultados en un vector de 1000 elementos:

(defn g[s](apply max(reduce #(assoc % %2(inc(apply max(take %2 %))))(into[](repeat 1e3 0))s)))

Por solicitud, con una declaración impresa (imprimirá la respuesta y devolverá cero). La entrada debe ser un vector (g [1 2 3]) o una lista (g '(1 2 3)):

(defn g[s](prn(apply max(reduce #(assoc % %2(inc(apply max(take %2 %))))(into[](repeat 1e3 0))s))))

Haskell, 58 57 56 caracteres

(x:s)%v|v>x=x:s%v|0<1=v:s
_%v=[v]
l s=length$foldl(%)[]s

Esto usa un algoritmo que vi una vez en Internet, pero no puedo encontrarlo. Lleva una cantidad de tiempo imperceptible en el caso de prueba dado en mi computadora con GHCi (probablemente sería aún más rápido si se compilara).

GolfScript, 35 caracteres

~]]){1${~2$<*)}%1+$-1>[\+]+}/$-1=0=

Una implementación que funciona como un programa completo con entrada en STDIN (sin el número de longitud proporcionado). La implementación es razonablemente rápida, incluso para entradas más largas (intente aquí ).

Ejemplos:

> 1 5 7 1 8 4 3 5
4

> 5 1 9 9 1 5
2

Ruby, 67

s=Hash.new{|s,a|f,*r=a
s[a]=f ?[1+s[r.select{|x|x>f}],s[r]].max: 0}

Esto se ejecuta en 30 segundos en la entrada grande, ¿eso cuenta de manera oportuna? :pag

Es una recursión bruta, pero con cierta memorización.

C #, 172 92 caracteres

Nada especial, pero lo hice, así que pensé que podría enviarlo.

int a(int[] j){int c=2,m=2,i=1;for(;++i<j.Length;){c=j[i]>j[i-1]?c+1:2;m=c>m?c:m;}return m;}

¡Gracias Armin y Bob por sus mejoras!

J , 19 bytes

[:#]`I.`[} ::,~/@|.

Pruébalo en línea!

Se ejecuta en O (n log n) , utilizando un orden de paciencia modificado ya que solo se necesita la longitud, no la subsecuencia real.

Explicación

[:#]`I.`[} ::,~/@|.  Input: array
                 |.  Reverse
               /     Reduce right-to-left
     I.                Find the index to insert while keeping it sorted
                       (uses binary search)
         }             Amend the current search array at that index with the next value
           ::          If error (when the index is not found)
             ,           Append the value at the end
 #                   Length of that array

Bash + coreutils, 131 bytes

Esta solución falla horriblemente en el requisito de manera oportuna , y ni siquiera es particularmente corta, pero me gustó que este tipo de cosas sea al menos teóricamente posible en el script de shell, por lo que estoy publicando de todos modos. Esto funciona con una complejidad de tiempo que induce la eternidad de O (2 ^ n).

s=${1//,/,:\},\{}
a=`eval echo "{$s,:}"`
for s in $a;{
b="$(tr , \\n<<<$s|grep -v :)"
sort -nC<<<"$b"&&wc -w<<<$b
}|sort -nr|sed 1q

La entrada es una lista separada por comas que se pasa como un único argumento de línea de comandos:

$ time ./slisc.sh 1,5,7,1,8,4,3,5
4

real    0m1.240s
user    0m0.518s
sys 0m0.689s
$ 

La expansión de llaves se usa para construir la lista de todas las subsecuencias posibles.

• La primera línea reemplaza comas con ,:},{, que produce una cadena como1,:},{5,:},{7,:},{1,:},{8,:},{4,:},{3,:},{5
• La segunda línea completa esta cadena con llaves, comas y punto y coma para dar esto {1,:},{5,:},{7,:},{1,:},{8,:},{4,:},{3,:},{5,:}. Esta es una expansión válida de llaves, que cuando se evaledita con un echoproduce esta lista separada por espacios1,5,7,1,8,4,3,5 1,5,7,1,8,4,3,: 1,5,7,1,8,4,:,5 1,5,7,1,8,4,:,: ...
• de forma predeterminada, bash divide las cadenas con espacios en blanco, por lo que recorremos cada elemento de esta lista:
  • las comas se reemplazan con nuevas líneas, luego se eliminan las líneas que contienen dos puntos, dando listas separadas por nuevas líneas para cada subsecuencia posible
  • luego, sort -Cpara probar el orden creciente, y si es así, utilizamos wc -wpara imprimir la longitud de la lista
• la lista resultante de longitudes de lista se ordena al revés y el primer valor se imprime para dar la mayor longitud de subsecuencia creciente.

Stax , 21 bytes

ë/NS7Γ╥╚┌{1╤╒¬è¶²╢╦┌☼

Ejecutar y depurarlo

Esto tiene dos casos de prueba, uno de los cuales es el caso de 1000 elementos. Se ejecuta ese en 24 segundos en mi máquina. Utiliza el enfoque clásico de programación dinámica para este tipo de problema.

J 34

Tenga en cuenta que también leo la entrada estándar.

>./;+/@:*&.>(<*>.)/\&.><\.".1!:1]3

Sin leer la entrada estándar, la carne tiene 26 caracteres.

>./;+/@:*&.>(<*>.)/\&.><\.

Acabo de notar que el mío corre lento para una gran entrada, oh bueno.

C ++ (gcc) , 129 bytes

int f(int*a,int n){int l[n]{},i=n,j,m=0;for(;i--;m=l[i]>m?l[i]:m)for(j=n;--j>i;)if(a[i]<a[j]&&l[i]<l[j]+1)l[i]=l[j]+1;return++m;}

Pruébalo en línea!

C # (.NET Core) , 155 bytes

Usó una matriz para calcular la subsecuencia creciente más larga que termina en cada posición en la matriz de entrada (programación dinámica), luego devolvió el valor más grande. Por ejemplo, la matriz calculada para la entrada [1,5,7,1,8,4,3,5]sería [1,2,3,1,4,2,2,3], y 4se devuelve el valor más grande .

int b(int[]x){int l=x.Length,r=1,i=0,j,c;var a=new int[l];a[0]=1;while(++i<l)for(j=0;j<i;j++){c=x[j]<x[i]?a[j]+1:1;a[i]=a[i]<c?c:a[i];r=r<c?c:r;}return r;}

Pruébalo en línea!

Wolfram Language (Mathematica) , 38 bytes

Length@LongestOrderedSequence[#,Less]&

Pruébalo en línea!

Por supuesto, hay un Mathematica incorporado para encontrar secuencias ordenadas más largas. Su nombre es muy largo: constituye más de la mitad de la solución, y no me sorprendería si alguien supera esta solución.