Longest increasing subsequence: Difference between revisions

=={{header|Prolog}}==

Works with SWI-Prolog version 6.4.1<br>

Naïve implementation.

<lang prolog>lis(In, Out) :-

% we asl Prolog to find the longest sequence

aggregate(max(N,Is), (one_is(In, [], Is), length(Is, N)), max(_, Res)),

reverse(Res, Out).

% we describe the way to find increasing subsequence

one_is([], Current, Current).

one_is([H | T], Current, Final) :-

( Current = [], one_is(T, [H], Final));

( Current = [H1 | _], H1 < H, one_is(T, [H | Current], Final));

one_is(T, Current, Final).

</lang>

Prolog finds the first longest subsequence

<pre> ?- lis([0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15], Out).

Out = [0,4,6,9,13,15].

?- lis([3,2,6,4,5,1], Out).

Out = [3,4,5].

</pre>