O desafio é escrever a implementação mais curta para encontrar a subsequência crescente mais longa .

Exemplo : Seja S a sequência 1 5 7 1 8 4 3 5 [comprimento de S = 8]

• Temos 1 sub-sequência de comprimento 0 [considerará crescente]
  
• 6 sub-seqüências de comprimento 1 {1,5,7,8,4,3} [todas elas são consideradas crescentes]
  
• (7 * 8) / 2 sub-sequências de comprimento 2 [mas removeremos duplicatas], as sub-sequências crescentes estão em preto forte.
  { 15,17 , 11, 18,14,13,57 , 51, 58 , 54,53,55,71, 78 , 74,73,75,84,83,85,43, 45,35 }
  

[observe que apenas estamos interessados ​​em sub sequências estritamente crescentes]

[você não pode alterar a ordem dos elementos dentro da sequência, portanto não há sub-sequência [37] na sequência de exemplo]

• Temos sub-sequências crescentes de comprimento 4, que são 1578, mas não há sub-sequência de comprimento 5, portanto, consideramos o comprimento da sub-sequência crescente mais longa = 4.
  

Entrada :

a ₁ a ₂ ... a _N (A sequência)

todos os números são números inteiros positivos menores que 10 ³
N <= 1000

Saída :

Um número inteiro que denota o comprimento da subseqüência crescente mais longa da sequência 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

Seu código deve ser executado em tempo hábil . Teste-o neste caso antes de enviá-lo aqui (também o link contém minha solução c ++ 11 de 290 bytes)

Você pode pegar a entrada de um arquivo / stdin ou como um parâmetro de função e pode imprimir a saída em um arquivo / stdout ou simplesmente retornar o valor se escrever uma função

Placar

1. Dennis CJam - 22
2. isaacg Pyth - 26
3. Howard GolfScript - 35
4. orgulhoso haskeller Haskell - 56
5. Ray Python 3-66
6. histocrata 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

Experimente online.

Exemplo

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

O programa imprime 57para este caso de teste após 0,25 segundos.

Como funciona

Peguei a ideia geral da resposta 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)).                     ";

Python 3, 66

Observe que todos os números estão no intervalo [1, 999], podemos usar uma matriz bpara manter o maior comprimento de subsequência que termina com cada número. b[x] = dsignifica que a subsequência mais longa que termina com xtem comprimento d. Para cada número da entrada, atualizamos o array usando b[x] = max(b[:x]) + 1e, em seguida, concluímos o trabalho, max(b)finalmente.

A complexidade do tempo é Em) O (mn) , onde mé sempre 1000 e né o 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)

Uau, parece que já foi destruído :) Você pode testá-lo usando stdin / stdout adicionando uma linha:

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

Solução de porta da @ ray. Passa nos testes oficiais. Agora usa entrada STDIN separada por espaço, não chamada de função.

Execute da seguinte maneira:

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

Explicação:

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)

Tempo ilimitado:

Pyth , 18

L?eS,ytbhyf>Thbbb0

Nota técnica: notei um bug no meu Pyth complier enquanto escrevia este golfe. Lnão estava funcionando. É por isso que há um commit recente no repositório git acima.

Clojure, 94 caracteres

Usando a abordagem de atualização de @ Ray em um vetor de 1000 itens:

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

Por solicitação, com declaração de impressão (imprimirá resposta e retornará nulo). A entrada deve ser um vetor (g [1 2 3]) ou uma 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

Isso usa um algoritmo que vi uma vez na internet, mas não consigo encontrá-lo. Leva um tempo imperceptível no caso de teste fornecido no meu computador com GHCi (provavelmente seria ainda mais rápido se fosse compilado).

GolfScript, 35 caracteres

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

Uma implementação que funciona como um programa completo com entrada no STDIN (sem o número especificado). A implementação é razoavelmente rápida, mesmo para entradas mais longas (tente aqui ).

Exemplos:

> 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}

Isso é executado em 30 segundos na entrada grande, isso conta como uma maneira oportuna? : p

É uma recursão bruta, mas com alguma memorização.

C #, 172 92 caracteres

Nada de especial, mas eu fiz isso e achei que poderia enviá-lo.

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;}

Obrigado Armin e Bob por suas melhorias!

J , 19 bytes

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

Experimente online!

É executado em O (n log n) , usando uma classificação de paciência modificada, pois somente o comprimento, e não a subsequência real, é necessário.

Explicação

[:#]`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

Essa solução falha horrivelmente no requisito de maneira oportuna e não é nem um pouco curta, mas eu gostei que esse tipo de coisa seja pelo menos teoricamente possível no shell script, então estou postando assim mesmo. Isso é executado com uma complexidade de tempo indutora de eternidade 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

Entrada é uma lista separada por vírgula passada como um único argumento de linha de comando:

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

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

A expansão entre chaves é usada para criar a lista de todas as subsequências possíveis.

• A primeira linha substitui vírgulas por ,:},{, que produz uma sequência como1,:},{5,:},{7,:},{1,:},{8,:},{4,:},{3,:},{5
• A segunda linha completa essa sequência com chaves, vírgulas e ponto e vírgula para fornecer isso {1,:},{5,:},{7,:},{1,:},{8,:},{4,:},{3,:},{5,:}. Essa é uma expansão de bash brace válida que, quando evaleditada com, echoproduz essa lista separada por espaço1,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,:,: ...
• por padrão, o bash divide as strings com espaços em branco, então fazemos um loop sobre cada elemento desta lista:
  • vírgulas são substituídas por novas linhas e, em seguida, as linhas contendo dois pontos são removidas, fornecendo listas separadas por novas linhas para cada subsequência possível
  • então sort -Ctestamos a ordem crescente e, em caso afirmativo, usamos wc -wpara imprimir o comprimento da lista
• a lista resultante de comprimentos de lista é classificada em ordem inversa e o primeiro valor impresso para fornecer o maior comprimento de subsequência crescente.

Stax , 21 bytes

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

Execute e depure

Isso tem dois casos de teste, um dos quais é o caso de 1000 elementos. Ele executa esse em 24 segundos na minha máquina. Ele usa a abordagem clássica de programação dinâmica para esse tipo de problema.

J 34

Note que eu também li entradas padrão.

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

Sem ler a entrada padrão, a carne tem 26 caracteres.

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

Só notei que o meu corre devagar para grandes entradas, tudo bem.

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;}

Experimente online!

C # (.NET Core) , 155 bytes

Usou uma matriz para calcular a subsequência crescente mais longa que termina em cada posição na matriz de entrada (programação dinâmica) e, em seguida, retornou o maior valor. Por exemplo, a matriz computada para entrada[1,5,7,1,8,4,3,5] seria [1,2,3,1,4,2,2,3]e o maior valor 4será retornado.

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;}

Experimente online!

Wolfram Language (Mathematica) , 38 bytes

Length@LongestOrderedSequence[#,Less]&

Experimente online!

Obviamente, existe um Mathematica embutido para encontrar sequências ordenadas mais longas. Seu nome é muito longo: compõe mais da metade da solução, e não ficarei surpreso se alguém vencer essa solução.