Wyzwanie polega na napisaniu najkrótszej implementacji w celu znalezienia najdłuższego rosnącego podsekwencji .

Przykład : Niech S będzie sekwencją 1 5 7 1 8 4 3 5 [długość S = 8]

• Mamy 1 podsekwencję o długości 0 [uzna, że ​​rośnie]
  
• 6 podsekwencji o długości 1 {1,5,7,8,4,3} [wszystkie uważa się za rosnące]
  
• (7 * 8) / 2 podsekwencje o długości 2 [ale usuniemy duplikaty], rosnąca podsekwencja ma mocną czerń.
  { 15,17 , 11, 18,14,13,57 , 51, 58 , 54,53,55,71, 78 , 74,73,75,84,83,85,43, 45,35 }
  

[zauważ, że interesują nas tylko ściśle rosnące podsekwencje]

[nie można zmienić kolejności elementów w sekwencji, więc w podanej sekwencji nie ma podsekwencji [37]]

• Mamy rosnące podsekwencje o długości 4, która wynosi 1578, ale nie ma podsekwencji o długości 5, więc rozważamy długość najdłużej rosnącej pod-sekwencji = 4.
  

Wejście :

a ₁ a ₂ ... a _N (Sekwencja)

wszystkie liczby są dodatnimi liczbami całkowitymi mniejszymi niż 10 ³
N <= 1000

Wyjście :

Jedna liczba całkowita oznaczająca długość najdłuższej wzrastającej pod-sekwencji sekwencji wejściowej.

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

Twój kod powinien zostać uruchomiony w odpowiednim czasie, przetestuj kod w tej sprawie przed przesłaniem go tutaj (również link zawiera moje 290-bajtowe rozwiązanie c ++ 11)

Możesz pobrać dane wejściowe z pliku / standardowego wejścia lub jako parametr funkcji i możesz wydrukować dane wyjściowe do pliku / standardowego wyjścia lub po prostu zwrócić wartość, jeśli napiszesz funkcję

Tablica wyników

1. Dennis CJam - 22
2. isaacg Pyth - 26
3. Howard GolfScript - 35
4. dumny haskeller Haskell - 56
5. Ray Python 3 - 66
6. histocrat Ruby - 67
7. DLeh C # - 92
8. Yosemite Mark Clojure - 94
9. faubiguy Python 3 - 113

CJam, 22 bajty

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

Wypróbuj online.

Przykład

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

Program drukuje 57dla tego przypadku testowego po 0,25 sekundy.

Jak to działa

Wziąłem ogólny pomysł z odpowiedzi @ 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

Zauważ, że wszystkie liczby są w zakresie [1, 999], możemy użyć tablicy, baby zachować najdłuższą długość podsekwencji kończącą się każdą liczbą. b[x] = doznacza, że ​​najdłuższa podsekwencja kończąca się na xma długość d. Dla każdej liczby z danych wejściowych aktualizujemy tablicę za pomocą, b[x] = max(b[:x]) + 1a następnie wykonujemy zadanie, biorąc w max(b)końcu.

Złożoność czasu jest Na) O (mn) , gdzie mzawsze wynosi 1000 i njest liczbą elementów wejściowych.

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

Wow, wygląda na to, że już nie jest golfem :) Możesz to przetestować używając stdin / stdout, dodając wiersz:

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

Port rozwiązania @ ray. Przechodzi oficjalne testy. Teraz wykorzystuje wejście STDIN rozdzielone spacjami, a nie wywołanie funkcji.

Uruchom w następujący sposób:

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

Wyjaśnienie:

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)

Czas nieograniczony:

Pyth , 18 lat

L?eS,ytbhyf>Thbbb0

Uwaga techniczna: Podczas pisania tego golfa zauważyłem błąd w moim kompilatorze Pyth. Lnie działał. Dlatego ostatnio zatwierdzono powyższe repozytorium git.

Clojure, 94 znaków

Stosując podejście @ Ray do aktualizowania wyników w wektorze 1000 elementów:

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

Na żądanie, z instrukcją print (wydrukuje odpowiedź i zwróci zero). Dane wejściowe powinny być wektorem (g [1 2 3]) lub listą (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 znaków

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

Korzysta z algorytmu, który widziałem raz w Internecie, ale nie mogę go znaleźć. Zajmuje to niezauważalnie dużo czasu w danym przypadku testowym na moim komputerze z GHCi (prawdopodobnie byłby nawet szybszy, gdyby został skompilowany).

GolfScript, 35 znaków

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

Implementacja działająca jako kompletny program z wejściem na STDIN (bez podanego numeru długości). Implementacja jest dość szybka, nawet przy dłuższych nakładach (spróbuj tutaj ).

Przykłady:

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

To działa w 30 sekund na dużym wejściu, czy to liczy się jako terminowe? : p

To brutalna rekurencja, ale z pewną zapamiętywaniem.

C #, 172 92 znaków

Nic specjalnego, ale zrobiłem to, więc pomyślałem, że równie dobrze mogę to zgłosić.

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

Dzięki Armin i Bob za ich ulepszenia!

J , 19 bajtów

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

Wypróbuj online!

Działa w O (n log n) , używając zmodyfikowanego sortowania cierpliwości, ponieważ potrzebna jest tylko długość, a nie faktyczna podsekwencja.

Wyjaśnienie

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

To rozwiązanie strasznie zawodzi w wymaganiach dotyczących terminowości i nie jest nawet szczególnie krótkie, ale podobało mi się, że tego rodzaju rzeczy są przynajmniej teoretycznie możliwe w skrypcie powłoki, więc i tak publikuję. Działa to z indukującą wieczność złożonością czasową 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

Dane wejściowe to lista rozdzielana przecinkami przekazywana jako pojedynczy argument wiersza poleceń:

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

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

Rozwijanie nawiasów służy do budowania listy wszystkich możliwych podsekwencji.

• Pierwszy wiersz zastępuje przecinki ,:},{, co daje ciąg podobny do1,:},{5,:},{7,:},{1,:},{8,:},{4,:},{3,:},{5
• Drugi wiersz uzupełnia ten ciąg nawiasami klamrowymi, przecinkami i średnikami, aby to dać {1,:},{5,:},{7,:},{1,:},{8,:},{4,:},{3,:},{5,:}. Jest to poprawne rozszerzenie nawiasu klamrowego, które po evaledycji z echotworzy listę oddzieloną spacjami1,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,:,: ...
• domyślnie bash dzieli ciągi znaków spacją, więc zapętlamy każdy element tej listy:
  • przecinki są zastępowane znakami nowej linii, a następnie linie zawierające dwukropki są usuwane, co daje listy rozdzielone znakiem nowej linii dla każdego możliwego podsekwencji
  • następnie sort -Ctestujemy rosnącą kolejność, a jeśli tak, użyj wc -wdo wydrukowania długości listy
• wynikowa lista długości list jest sortowana w odwrotnej kolejności, a pierwsza wartość drukowana w celu uzyskania najdłuższej wzrastającej długości podsekwencji.

Stax , 21 bajtów

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

Uruchom i debuguj

Ma to dwa przypadki testowe, z których jeden to przypadek 1000 elementów. Działa to w ciągu 24 sekund na moim komputerze. Wykorzystuje klasyczne podejście do programowania dynamicznego dla tego typu problemów.

J 34

Zauważ, że czytam również standardowe wejście.

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

Bez odczytu standardowego wejścia mięso ma 26 znaków.

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

Właśnie zauważyłem, że moje kopalnie działają wolno przy dużych nakładach, no cóż.

C ++ (gcc) , 129 bajtów

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

Wypróbuj online!

C # (.NET Core) , 155 bajtów

Użył tablicy do obliczenia najdłuższego rosnącego podsekwencji kończącego się na każdej pozycji w tablicy wejściowej (programowanie dynamiczne), a następnie zwrócił największą wartość. Na przykład obliczona tablica dla danych wejściowych [1,5,7,1,8,4,3,5]byłaby [1,2,3,1,4,2,2,3], a zwracana 4jest największa wartość .

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

Wypróbuj online!

Wolfram Language (Mathematica) , 38 bajtów

Length@LongestOrderedSequence[#,Less]&

Wypróbuj online!

Oczywiście jest wbudowana Mathematica do wyszukiwania najdłuższych uporządkowanych sekwencji. Jego nazwa jest bardzo długa: stanowi ponad połowę rozwiązania i nie zdziwię się, jeśli ktoś rozwiąże to rozwiązanie.