Longest Increasing Sequence (Dynamic Programming)

/* lis(As, Xs) is true if Xs is a longest strictly increasing sequence of    */
/*   elements occurring in As.                                               */
/* e.g. lis([59,43,49,37,51,25,8,51,28,21,7,75,5,54,87,13,34,92,97,2], Xs).  */
/* gives Xs=[43,49,51,54,87,92,97]                                           */
lis(As, Xs):-
  lis_1(As, As, [], Ls),
  max(Ls, Maximum),
  reverse(As, As1),
  reverse(Ls, Ls1),
  lis_3(Maximum, Ls1, As1, [], Xs).

% Find length of longest increasing sequence ending at each element of As...
lis_1([], _, Ls, Ls).
lis_1([Aj|As], AllAs, Ls0, Ls):-
  lis_2(Ls0, AllAs, Aj, 1, Lj),
  append(Ls0, [Lj], Ls1),
  lis_1(As, AllAs, Ls1, Ls).

% Find the length of the longest increasing sequence ending at A[j]...
lis_2([], _, _, Lj, Lj).
lis_2([Li|Ls], [Ai|As], Aj, Lj0, Lj):-
  Aj > Ai, % Strictly increasing
  Li + 1 > Lj0, !,
  Lj1 is Li + 1,
  lis_2(Ls, As, Aj, Lj1, Lj).
lis_2([_|Ls], [_|As], Aj, Lj0, Lj):-
  lis_2(Ls, As, Aj, Lj0, Lj).

% Extract the sequence from the list of lengths in Ls...
lis_3(0, _, _, Xs, Xs):-!.
lis_3(I, [I|Ls], [A|As], Xs0, Xs):-!,
  I1 is I - 1,
  lis_3(I1, Ls, As, [A|Xs0], Xs).
lis_3(I, [_|Ls], [_|As], Xs0, Xs):-
  lis_3(I, Ls, As, Xs0, Xs).

/* max(List, Max) is true if Max is the largest element in List.             */
max([X|Xs], Y):-max_1(Xs, X, Y).

max_1([], X, X):-!.
max_1([Y|Ys], X, Z):-Y >= X, !, max_1(Ys, Y, Z).
max_1([_|Ys], X, Z):-max_1(Ys, X, Z).

/* append(Xs, Ys, Zs) is true if Zs is the result of appending the list Xs   */
/*   to the list Ys.                                                         */
%append([], Ys, Ys).
%append([X|Xs], Ys, [X|Zs]):-append(Xs, Ys, Zs).

/* reverse(Xs, Ys) is true if Ys is the result of reversing the order of     */
/*   the elements in the list Xs.                                            */
%reverse(Xs, Ys):-reverse_1(Xs, [], Ys).

%reverse_1([], As, As).
%reverse_1([X|Xs], As, Ys):-reverse_1(Xs, [X|As], Ys).

LPA Index     Home Page