niekoniecznie spójny oznacza że nie musi to być a[i],a[i+1],...a[i+k] ale
a[i],a[j],...a[k] tże 1<=i

Prosze o jakies testy do zadania... jakies takies z haczykiem bo przykladowy test wychodzi a SPOJ odrzuca
Tesciki tesciki

Dzieki z góry!

Nie zakładam nowego wątku tylko się podczepię tutaj. Na początek kilka wniosków:

1. W zadaniu chodzi o znalezienie najdłuższego wspólnego niekoniecznie spójnego podciągu (czyli o to co jest opisane w sekcji "Wyjście"). Nie wiem dlaczego autor każe Jasiowi w treści zadania pytać o podciąg rosnący. By uniknąć konfuzji proponuję by zmienić treść pytania Jasia np. na "Co dziś na obiad?"

2. Zestawy danych testowych nie są zgodne ze specyfikacją. Ciąg Fasoli zawiera powtórzone liczby, co łatwo sprawdzić programem:
   [code]#include

include

include

int main(void) {
int i, n, t;
char mark[25501];

// n
scanf("%d", &n);

// ciag jasia
memset(mark, 0, sizeof(mark));
for (i = 0; i < n; ++i) {
	scanf("%d", &t);
	assert(mark[t] == 0);
	mark[t] = 1;
}

// ciag fasoli
memset(mark, 0, sizeof(mark));
for (i = 0; i < n; ++i) {
	scanf("%d", &t);
	assert(mark[t] == 0);
	mark[t] = 1;
}
return 0;

}[/code]W programie zaznaczamy w tablicy mark każdą wczytaną liczbę. Program wyleci na drugim assercie (SIGABRT)

1. Nawet mając na uwadze powyższe program użyty przez autora do wygenerowania "poprawnych" wyników sam najprawdopodobniej był błędny. Przykład:
   7
   1 4 2 6 3 5 7
   4 2 7 2 6 3 3
   Najdłuższy wspólny niekoniecznie spójny podciąg to np. 4, 2, 6, 3, jednak mój program który zwracał 4 wylatywał ze statusem WA, zaakceptowany został natomiast program który zwracał odpowiedź... 6 (sic!), uwzględniając wszystkie "powtórzone" elementy, czyli robiąc z tego ciąg 4, 2, 2, 6, 3, 3

Inne testy:
5
4 1 5 3 2
1 4 3 5 5
program który dostaje WA: 2
program który dostaje AC: 3

7
4 3 1 6 5 7 2
3 7 2 7 6 2 1
program który dostaje WA: 3
program który dostaje AC: 4

6
2 4 6 5 1 3
2 1 5 2 2 1
program który dostaje WA: 3
program który dostaje AC: 4

Dla nie powtórzonych liczb w ciągu oba programy zwracają takie same wyniki, czyli dla danych:
10
9 4 2 8 3 7 1 6 5 10
5 9 8 3 10 1 6 2 4 7
oba zwrócą 5, jednak wydaje mi się że większość SPOJowiczów poległa właśnie na owym niezgodnym ze specyfikacją teście, którego rozwiązaniem wydaje się nie być wcale długość najdłuższego wspólnego niekoniecznie spójnego podciągu, tylko długość przedstawionej przeze mnie "hybrydy" z powtórzeniami.

1. Oczywiście istnieje prawdopodobieństwo, że mój program dostał AC przez przypadek, ale cóż - nikt nie jest doskonały

http://pl.spoj.com/problems/STAMPSLO/1

1) Czy ktoś wie co dokładnie należy zrobić z powtarzającymi się liczbami w drugim ciągu?

2) Tu wrzucam prosty kod, który powinien dawać przynajmniej TLE, a dostaje WA.

import sys

data = sys.stdin.readlines()

n = int(data[0])
nums1 = map(int, data[1].split())
nums2 = map(int, data[2].split())

def unique_everseen(seq):
    seen = set()
    seen_add = seen.add
    return [x for x in seq if not (x in seen or seen_add(x))]

nums1 = unique_everseen(nums1)
nums2 = unique_everseen(nums2)

index = [0]*(n+1)
for i, num in enumerate(nums1):
    index[num] = i

tree = [0]*n
for num in nums2:
    q = max( tree[0 : index[num]+1] )
    tree[ index[num] ] = q+1

print max(tree)

Update 2020
Wygląda na to, ze ktoś częściowo poprawił testy. Nadal występują powtórzenia w drugim ciągu, ale nie należy ich brać pod uwagę.
U mnie przeszedł program, który zwracał poprawne wyniki (nie takie jak napisał chakier).

Czyli raczej nic się tu nie zmieniło - były i są powtórzenia tylko w drugim ciągu więc jednak nic nikt nie poprawił nawet częściowo i jest duże prawdopodobieństwo, że mój program dostał AC tylko przez przypadek, tym bardziej, że mój Ac program raczej też odwrotnie [poprawnie] “odpowiadał” na testy @chakier’a . Sprawdziłem wprawdzie tylko 2 pierwsze testy.