Prolog - Finding the longest increasing subsequence

Question

I want to solve the following exercise in Prolog:

For a list of integers Zs, max_sequence(Zs,Xs) finds a longest increasing subsequence Xs.

Sample queries:

?- max_sequence([1,2,1,2,3,4,2,1,2,1],Xs).
Xs = [1,2,3,4].                                     % expected result

?- max_sequence([1,2,1,2,3,4,2,1,6,7,7,2,1,8],Xs).
Xs = [1,2,3,4,6,7,8].                               % expected result

I can't understand why... but my code is wrong, the result is always false.

max_sequence(L,R) :-
    cresc(L,[],R).

cresc([],[],[]).
cresc([H|T],C,[H|C]) :-
    maxList(H,C),
    \+ member(H,C),
    cresc(T,C,C).
cresc([H|T],C,C) :-
    member(H,C),
    cresc(T,C,C).       
cresc([H|T],C,C) :-
    \+ maxList(H,C),
    cresc(T,C,C).   

maxList(_,[]).
maxList(N, [H|T]) :-
    N>H,
    maxList(N,T).

I would like to know if my approach to the problem is correct. Thanks for any help!

Answer 1

I can't understand your approach at all, but using Trace command in swi-prolog you can see your program execution step by step to see where it fails. Try it and you will see what's wrong with your code.

Anyway this could be one possible solution: starting from the first element of the list you should simply collect a list until elements are increasing, keeping also the length of this sublist, this is the first candidate. Then start again collecting a new list and its length, and if is longer than the candidate, you switch them, and so on.. Here you can find the code: max_seqs , the first part.