⚠️ Warning: This is a draft ⚠️

This means it might contain formatting issues, incorrect code, conceptual problems, or other severe issues.

If you want to help to improve and eventually enable this page, please fork RosettaGit's repository and open a merge request on GitHub.

{{task}} Calculate and show here a [[wp:Longest increasing subsequence|longest increasing subsequence]] of the list: :$\left\{3, 2, 6, 4, 5, 1\right\}$ And of the list: :$\left\{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15\right\}$

Note that a list may have more than one subsequence that is of the maximum length.

;Ref:

# An efficient solution can be based on [[wp:Patience sorting|Patience sorting]].

## 360 Assembly

{{trans|VBScript}}

```*        Longest increasing subsequence    04/03/2017
LNGINSQ  CSECT
USING  LNGINSQ,R13        base register
B      72(R15)            skip savearea
DC     17F'0'             savearea
STM    R14,R12,12(R13)    save previous context
ST     R13,4(R15)         link backward
ST     R15,8(R13)         link forward
LR     R13,R15            set addressability
LA     R6,1             i=1
DO WHILE=(CH,R6,LE,=H'2') do i=1 to 2
IF CH,R6,EQ,=H'1' THEN      if i=1 then
MVC    N,=AL2((A2-A1)/2)    n=hbound(a1)
MVC    AA(64),A1            a=a1
ELSE     ,                  else
MVC    N,=AL2((AA-A2)/2)    n=hbound(a2)
MVC    AA(64),A2            a=a2
ENDIF    ,                  endif
MVC    PG,=CL80': '       init buffer
LA     R2,AA-2            @a
LH     R3,N               n
BAL    R14,PRINT          print a
MVC    LL,=H'0'           l=0
SR     R7,R7              j=0
DO WHILE=(CH,R7,LE,N)       do j=0 to n
MVC    LO,=H'1'             lo=1
MVC    HI,LL                hi=l
LH     R4,LO                lo
DO WHILE=(CH,R4,LE,HI)        do while lo<=hi
LH     R1,LO                  lo
AH     R1,HI                  lo+hi
SRA    R1,1                   /2
STH    R1,MIDDLE              middle=(lo+hi)/2
SLA    R1,1                   *2
LH     R1,MM(R1)              m(middle+1)
SLA    R1,1                   *2
LH     R3,AA(R1)              r3=a(m(middle+1)+1)
LR     R1,R7                  j
SLA    R1,1                   *2
LH     R4,AA(R1)              r4=a(j+1)
LH     R2,MIDDLE              middle
IF CR,R3,LT,R4 THEN             if a(m(middle+1)+1)<a(j+1) then
LA     R2,1(R2)                 middle+1
STH    R2,LO                    lo=middle+1
ELSE     ,                      else
BCTR   R2,0                     middle-1
STH    R2,HI                    hi=middle-1
ENDIF    ,                      endif
LH     R4,LO                  lo
ENDDO    ,                    end /*while*/
LH     R10,LO               newl=lo
LR     R1,R10               newl
SLA    R1,1                 *2
LH     R3,MM-2(R1)          m(newl)
LR     R1,R7                j
SLA    R1,1                 *2
STH    R3,PP(R1)            p(j+1)=m(newl)
LR     R1,R10               newl
SLA    R1,1                 *2
STH    R7,MM(R1)            m(newl+1)=j
IF CH,R10,GT,LL               if newl>l then
STH    R10,LL                 l=newl
ENDIF    ,                    endif
LA     R7,1(R7)             j++
ENDDO    ,                  enddo j
LH     R1,LL              l
SLA    R1,1               *2
LH     R10,MM(R1)         k=m(l+1)
LH     R7,LL              j=l
DO WHILE=(CH,R7,GE,=H'1')   do j=l to 1 by -1
LR     R1,R10               k
SLA    R1,1                 *2
LH     R2,AA(R1)            a(k+1)
LR     R1,R7                j
SLA    R1,1                 *2
STH    R2,SS-2(R1)          s(j)=a(k+1)
LR     R1,R10               k
SLA    R1,1                 *2
LH     R10,PP(R1)           k=p(k+1)
BCTR   R7,0                 j--
ENDDO    ,                  enddo j
MVC    PG,=CL80'> '       init buffer
LA     R2,SS-2            @s
LH     R3,LL              l
BAL    R14,PRINT          print a
LA     R6,1(R6)           i++
ENDDO    ,                enddo i
L      R13,4(0,R13)       restore previous savearea pointer
LM     R14,R12,12(R13)    restore previous context
XR     R15,R15            rc=0
BR     R14                exit
PRINT    LA     R10,PG        ---- print subroutine
LA     R10,2(R10)         pgi=2
LA     R7,1               j=1
DO WHILE=(CR,R7,LE,R3)      do j=1 to nx
LR     R1,R7                j
SLA    R1,1                 *2
LH     R1,0(R2,R1)          x(j)
XDECO  R1,XDEC              edit x(j)
MVC    0(3,R10),XDEC+9      output x(j)
LA     R10,3(R10)           pgi+=3
LA     R7,1(R7)             j++
ENDDO    ,                  enddo j
XPRNT  PG,L'PG            print buffer
BR     R14           ---- return
A1       DC     H'3',H'2',H'6',H'4',H'5',H'1'
A2       DC     H'0',H'8',H'4',H'12',H'2',H'10',H'6',H'14'
DC     H'1',H'9',H'5',H'13',H'3',H'11',H'7',H'15'
AA       DS     32H                a(32)
PP       DS     32H                p(32)
MM       DS     32H                m(32)
SS       DS     32H                s(32)
N        DS     H                  n
LL       DS     H                  l
LO       DS     H                  lo
HI       DS     H                  hi
MIDDLE   DS     H                  middle
PG       DS     CL80               buffer
XDEC     DS     CL12               temp for xdeco
YREGS
END    LNGINSQ
```

{{out}}

```
:   3  2  6  4  5  1
>   2  4  5
:   0  8  4 12  2 10  6 14  1  9  5 13  3 11  7 15
>   0  2  6  9 11 15

```

## AutoHotkey

```Lists := [[3,2,6,4,5,1], [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]]

for k, v in Lists {
D := LIS(v)
MsgBox, % D[D.I].seq
}

LIS(L) {
D := []
for i, v in L {
D[i, "Length"] := 1, D[i, "Seq"] := v, D[i, "Val"] := v
Loop, % i - 1 {
if(D[A_Index].Val < v && D[A_Index].Length + 1 > D[i].Length) {
D[i].Length := D[A_Index].Length + 1
D[i].Seq := D[A_Index].Seq ", " v
if (D[i].Length > MaxLength)
MaxLength := D[i].Length, D.I := i
}
}
}
return, D
}
```

'''Output:'''

```3, 4, 5
0, 4, 6, 9, 13, 15
```

## C

Using an array that doubles as linked list (more like reversed trees really). O(n) memory and O(n2) runtime.

```#include <stdio.h>
#include <stdlib.h>

struct node {
int val, len;
struct node *next;
};

void lis(int *v, int len)
{
int i;
struct node *p, *n = calloc(len, sizeof *n);
for (i = 0; i < len; i++)
n[i].val = v[i];

for (i = len; i--; ) {
// find longest chain that can follow n[i]
for (p = n + i; p++ < n + len; ) {
if (p->val > n[i].val && p->len >= n[i].len) {
n[i].next = p;
n[i].len = p->len + 1;
}
}
}

// find longest chain
for (i = 0, p = n; i < len; i++)
if (n[i].len > p->len) p = n + i;

do printf(" %d", p->val); while ((p = p->next));
putchar('\n');

free(n);
}

int main(void)
{
int x[] = { 3, 2, 6, 4, 5, 1 };
int y[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };

lis(x, sizeof(x) / sizeof(int));
lis(y, sizeof(y) / sizeof(int));
return 0;
}
```

{{out}}

```
3 4 5
0 4 6 9 13 15

```

## C++

Patience sorting

```#include <iostream>
#include <vector>
#include <tr1/memory>
#include <algorithm>
#include <iterator>

template <typename E>
struct Node {
E value;
std::tr1::shared_ptr<Node<E> > pointer;
};

template <class E>
struct node_ptr_less {
bool operator()(const std::tr1::shared_ptr<Node<E> > &node1,
const std::tr1::shared_ptr<Node<E> > &node2) const {
return node1->value < node2->value;
}
};

template <typename E>
std::vector<E> lis(const std::vector<E> &n) {
typedef std::tr1::shared_ptr<Node<E> > NodePtr;

std::vector<NodePtr> pileTops;
// sort into piles
for (typename std::vector<E>::const_iterator it = n.begin(); it != n.end(); it++) {
NodePtr node(new Node<E>());
node->value = *it;
typename std::vector<NodePtr>::iterator j =
std::lower_bound(pileTops.begin(), pileTops.end(), node, node_ptr_less<E>());
if (j != pileTops.begin())
node->pointer = *(j-1);
if (j != pileTops.end())
*j = node;
else
pileTops.push_back(node);
}
// extract LIS from piles
std::vector<E> result;
for (NodePtr node = pileTops.back(); node != NULL; node = node->pointer)
result.push_back(node->value);
std::reverse(result.begin(), result.end());
return result;
}

int main() {
int arr1[] = {3,2,6,4,5,1};
std::vector<int> vec1(arr1, arr1 + sizeof(arr1)/sizeof(*arr1));
std::vector<int> result1 = lis(vec1);
std::copy(result1.begin(), result1.end(), std::ostream_iterator<int>(std::cout, ", "));
std::cout << std::endl;

int arr2[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
std::vector<int> vec2(arr2, arr2 + sizeof(arr2)/sizeof(*arr2));
std::vector<int> result2 = lis(vec2);
std::copy(result2.begin(), result2.end(), std::ostream_iterator<int>(std::cout, ", "));
std::cout << std::endl;
return 0;
}
```

{{out}}

```2, 4, 5,
0, 2, 6, 9, 11, 15,
```

## C#

### Recursive

{{works with|C sharp|6}}

```using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

public static class LIS
{
public static IEnumerable<T> FindRec<T>(IList<T> values, IComparer<T> comparer = null) =>
values == null ? throw new ArgumentNullException() :
FindRecImpl(values, Sequence<T>.Empty, 0, comparer ?? Comparer<T>.Default).Reverse();

private static Sequence<T> FindRecImpl<T>(IList<T> values, Sequence<T> current, int index, IComparer<T> comparer) {
if (index == values.Count) return current;
if (current.Length > 0 && comparer.Compare(values[index], current.Value) <= 0)
return FindRecImpl(values, current, index + 1, comparer);
return Max(
FindRecImpl(values, current, index + 1, comparer),
FindRecImpl(values, current + values[index], index + 1, comparer)
);
}

private static Sequence<T> Max<T>(Sequence<T> a, Sequence<T> b) => a.Length < b.Length ? b : a;

class Sequence<T> : IEnumerable<T>
{
public static readonly Sequence<T> Empty = new Sequence<T>(default(T), null);

public Sequence(T value, Sequence<T> tail)
{
Value = value;
Tail = tail;
Length = tail == null ? 0 : tail.Length + 1;
}

public T Value { get; }
public Sequence<T> Tail { get; }
public int Length { get; }

public static Sequence<T> operator +(Sequence<T> s, T value) => new Sequence<T>(value, s);

public IEnumerator<T> GetEnumerator()
{
for (var s = this; s.Length > 0; s = s.Tail) yield return s.Value;
}

IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
}
```

### Patience sorting

{{works with|C sharp|7}}

```public static class LIS
{
public static T[] Find<T>(IList<T> values, IComparer<T> comparer = null) {
if (values == null) throw new ArgumentNullException();
if (comparer == null) comparer = Comparer<T>.Default;
var pileTops = new List<T>();
var pileAssignments = new int[values.Count];
for (int i = 0; i < values.Count; i++) {
T element = values[i];
int pile = pileTops.BinarySearch(element, comparer);
if (pile < 0) pile = ~pile;
if (pile == pileTops.Count) pileTops.Add(element);
else pileTops[pile] = element;
pileAssignments[i] = pile;
}
T[] result = new T[pileTops.Count];
for (int i = pileAssignments.Length - 1, p = pileTops.Count - 1; p >= 0; i--) {
if (pileAssignments[i] == p) result[p--] = values[i];
}
return result;
}
}
```

## Clojure

Implementation using the Patience Sort approach. The elements (''newelem'') put on a pile combine the "card" with a reference to the top of the previous stack, as per the algorithm. The combination is done using ''cons'', so what gets put on a pile is a list -- a descending subsequence.

```(defn place [piles card]
(let [[les gts] (->> piles (split-with #(<= (ffirst %) card)))
newelem (cons card (->> les last first))
modpile (cons newelem (first gts))]
(concat les (cons modpile (rest gts)))))

(defn a-longest [cards]
(let [piles (reduce place '() cards)]
(->> piles last first reverse)))

(println (a-longest [3 2 6 4 5 1]))
(println (a-longest [0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15]))
```

{{out}} (2 4 5) (0 2 6 9 11 15)

```

## Common Lisp

### Common Lisp: Using the method in the video

Slower and more memory usage compared to the patience sort method.

```lisp
(defun longest-increasing-subseq (list)
(let ((subseqs nil))
(dolist (item list)
(let ((longest-so-far (longest-list-in-lists (remove-if-not #'(lambda (l) (> item (car l))) subseqs))))
(push (cons item longest-so-far) subseqs)))
(reverse (longest-list-in-lists subseqs))))

(defun longest-list-in-lists (lists)
(let ((longest nil)
(longest-len 0))
(dolist (list lists)
(let ((len (length list)))
(when (> len longest-len)
(setf longest list
longest-len len))))
longest))

(dolist (l (list (list 3 2 6 4 5 1)
(list 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15)))
(format t "~A~%" (longest-increasing-subseq l))))
```

{{out}}

```(2 4 5)
(0 2 6 9 11 15)
```

### Common Lisp: Using the Patience Sort approach

This is 5 times faster and and uses a third of the memory compared to the approach in the video.

```(defun lis-patience-sort (input-list)
(let ((piles nil))
(dolist (item input-list)
(setf piles (insert-item item piles)))
(reverse (caar (last piles)))))

(defun insert-item (item piles)
(let ((not-found t))
(loop
while not-found
for pile in piles
and prev = nil then pile
and i from 0
do (when (<= item (caar pile))
(setf (elt piles i) (push (cons item (car prev)) (elt piles i))
not-found nil)))
(if not-found
(append piles (list (list (cons item (caar (last piles))))))
piles)))

(dolist (l (list (list 3 2 6 4 5 1)
(list 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15)))
(format t "~A~%" (lis-patience-sort l)))
```

{{out}}

```(2 4 5)
(0 2 6 9 11 15)
```

===Common Lisp: Using the Patience Sort approach (alternative)=== This is a different version of the code above.

```(defun insert-item (item piles)
(multiple-value-bind
(i prev)
(do* ((prev nil (car x))
(x piles (cdr x))
(i 0 (1+ i)))
((or (null x) (<= item (caaar x))) (values i prev)))
(if (= i (length piles))
(append piles (list (list (cons item (caar (last piles))))))
(progn (push (cons item (car prev)) (elt piles i))
piles))))

(defun longest-inc-seq (input)
(do* ((piles nil (insert-item (car x) piles))
(x input (cdr x)))
((null x) (reverse (caar (last piles))))))

(dolist (l (list (list 3 2 6 4 5 1)
(list 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15)))
(format t "~A~%" (longest-inc-seq l)))
```

{{out}}

```(2 4 5)
(0 2 6 9 11 15)
```

## D

### Simple Version

{{trans|Haskell}} Uses the second powerSet function from the Power Set Task.

```import std.stdio, std.algorithm, power_set2;

T[] lis(T)(T[] items) pure nothrow {
//return items.powerSet.filter!isSorted.max!q{ a.length };
return items
.powerSet
.filter!isSorted
.minPos!q{ a.length > b.length }
.front;
}

void main() {
[3, 2, 6, 4, 5, 1].lis.writeln;
[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15].lis.writeln;
}
```

{{out}}

```[2, 4, 5]
[0, 2, 6, 9, 11, 15]
```

### Patience sorting

{{trans|Python}} From the second Python entry, using the Patience sorting method.

```import std.stdio, std.algorithm, std.array;

/// Return one of the Longest Increasing Subsequence of
/// items using patience sorting.
T[] lis(T)(in T[] items) pure nothrow
if (__traits(compiles, T.init < T.init))
out(result) {
assert(result.length <= items.length);
assert(result.isSorted);
assert(result.all!(x => items.canFind(x)));
} body {
if (items.empty)
return null;

static struct Node { T val; Node* back; }
auto pile = [[new Node(items[0])]];

OUTER: foreach (immutable di; items[1 .. \$]) {
foreach (immutable j, ref pj; pile)
if (pj[\$ - 1].val > di) {
pj ~= new Node(di, j ? pile[j - 1][\$ - 1] : null);
continue OUTER;
}
pile ~= [new Node(di, pile[\$ - 1][\$ - 1])];
}

T[] result;
for (auto ptr = pile[\$ - 1][\$ - 1]; ptr != null; ptr = ptr.back)
result ~= ptr.val;
result.reverse();
return result;
}

void main() {
foreach (d; [[3,2,6,4,5,1],
[0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]])
d.lis.writeln;
}
```

The output is the same.

### Faster Version

{{trans|Java}} With some more optimizations.

```import std.stdio, std.algorithm, std.range, std.array;

T[] lis(T)(in T[] items) pure nothrow
if (__traits(compiles, T.init < T.init))
out(result) {
assert(result.length <= items.length);
assert(result.isSorted);
assert(result.all!(x => items.canFind(x)));
} body {
if (items.empty)
return null;

static struct Node {
T value;
Node* pointer;
}
Node*[] pileTops;
auto nodes = minimallyInitializedArray!(Node[])(items.length);

// Sort into piles.
foreach (idx, x; items) {
auto node = &nodes[idx];
node.value = x;
immutable i = pileTops.length -
pileTops.assumeSorted!q{a.value < b.value}
.upperBound(node)
.length;
if (i != 0)
node.pointer = pileTops[i - 1];
if (i != pileTops.length)
pileTops[i] = node;
else
pileTops ~= node;
}

// Extract LIS from nodes.
size_t count = 0;
for (auto n = pileTops[\$ - 1]; n != null; n = n.pointer)
count++;
auto result = minimallyInitializedArray!(T[])(count);
for (auto n = pileTops[\$ - 1]; n != null; n = n.pointer)
result[--count] = n.value;
return result;
}

void main() {
foreach (d; [[3,2,6,4,5,1],
[0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]])
d.writeln;
}
```

The output is the same.

```in-pair:
if = :nil dup:
false drop
else:
@in-pair &> swap &< dup

get-last lst:
get-from lst -- len lst

lis-sub pile i di:
for j range 0 -- len pile:
local :pj get-from pile j
if > &< get-last pj di:
push-to pj & di if j get-last get-from pile -- j :nil
return
push-to pile [ & di get-last get-last pile ]

lis d:
local :pile [ [ & get-from d 0 :nil ] ]
for i range 1 -- len d:
lis-sub pile i get-from d i
[ for in-pair get-last get-last pile ]

!. lis [ 3 2 6 4 5 1 ]
!. lis [ 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 ]

```

{{out}}

```[ 2 4 5 ]
[ 0 2 6 9 11 15 ]
```

## Elixir

{{trans|Erlang}}

### Naive version

very slow

```defmodule Longest_increasing_subsequence do
# Naive implementation
def lis(l) do
(for ss <- combos(l), ss == Enum.sort(ss), do: ss)
|> Enum.max_by(fn ss -> length(ss) end)
end

defp combos(l) do
Enum.reduce(1..length(l), [[]], fn k, acc -> acc ++ (combos(k, l)) end)
end
defp combos(1, l), do: (for x <- l, do: [x])
defp combos(k, l) when k == length(l), do: [l]
defp combos(k, [h|t]) do
(for subcombos <- combos(k-1, t), do: [h | subcombos]) ++ combos(k, t)
end
end

IO.inspect Longest_increasing_subsequence.lis([3,2,6,4,5,1])
IO.inspect Longest_increasing_subsequence.lis([0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15])
```

{{out}}

```
[3, 4, 5]
[0, 4, 6, 9, 13, 15]

```

### Patience sort version

```defmodule Longest_increasing_subsequence do
# Patience sort implementation
def patience_lis(l), do: patience_lis(l, [])

defp patience_lis([h | t], []), do: patience_lis(t, [[{h,[]}]])
defp patience_lis([h | t], stacks), do: patience_lis(t, place_in_stack(h, stacks, []))
defp patience_lis([], []), do: []
defp patience_lis([], stacks), do: get_previous(stacks) |> recover_lis |> Enum.reverse

defp place_in_stack(e, [stack = [{h,_} | _] | tstacks], prevstacks) when h > e do
prevstacks ++ [[{e, get_previous(prevstacks)} | stack] | tstacks]
end
defp place_in_stack(e, [stack | tstacks], prevstacks) do
place_in_stack(e, tstacks, prevstacks ++ [stack])
end
defp place_in_stack(e, [], prevstacks) do
prevstacks ++ [[{e, get_previous(prevstacks)}]]
end

defp get_previous(stack = [_|_]), do: hd(List.last(stack))
defp get_previous([]), do: []

defp recover_lis({e, prev}), do: [e | recover_lis(prev)]
defp recover_lis([]), do: []
end

IO.inspect Longest_increasing_subsequence.patience_lis([3,2,6,4,5,1])
IO.inspect Longest_increasing_subsequence.patience_lis([0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15])
```

{{out}}

```
[2, 4, 5]
[0, 2, 6, 9, 11, 15]

```

## Erlang

Both implementations:

• Patience sort version.

Function ''combos'' is copied from [http://panduwana.wordpress.com/2010/04/21/combination-in-erlang/ panduwana blog].

Function ''maxBy'' is copied from [http://stackoverflow.com/a/4762387/4162959 Hynek -Pichi- Vychodil's answer].

```
-module(longest_increasing_subsequence).

-export([test_naive/0, test_patience/0]).

% **************************************************
% Interface to test the implementation
% **************************************************

test_naive() ->
test_gen(fun lis/1).

test_patience() ->
test_gen(fun patience_lis/1).

test_gen(F) ->
show_result(F([3,2,6,4,5,1])),
show_result(F([0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15])).

show_result(Res) ->
io:format("~w\n", [Res]).

% **************************************************

% **************************************************
% Naive implementation
% **************************************************

lis(L) ->
maxBy(
fun(SS) -> length(SS) end,
[ lists:usort(SS)
||  SS <- combos(L),
SS == lists:sort(SS)]
).

% **************************************************

% **************************************************
% Patience sort implementation
% **************************************************

patience_lis(L) ->
patience_lis(L, []).

patience_lis([H | T], Stacks) ->
NStacks =
case Stacks of
[] ->
[[{H,[]}]];
_ ->
place_in_stack(H, Stacks, [])
end,
patience_lis(T, NStacks);
patience_lis([], Stacks) ->
case Stacks of
[] ->
[];
[_|_] ->
lists:reverse( recover_lis( get_previous(Stacks) ) )
end.

place_in_stack(E, [Stack = [{H,_} | _] | TStacks], PrevStacks) when H > E ->
PrevStacks ++ [[{E, get_previous(PrevStacks)} | Stack] | TStacks];
place_in_stack(E, [Stack = [{H,_} | _] | TStacks], PrevStacks) when H =< E ->
place_in_stack(E, TStacks, PrevStacks ++ [Stack]);
place_in_stack(E, [], PrevStacks)->
PrevStacks ++ [[{E, get_previous(PrevStacks)}]].

get_previous(Stack = [_|_]) ->
hd(lists:last(Stack));
get_previous([]) ->
[].

recover_lis({E,Prev}) ->
[E|recover_lis(Prev)];
recover_lis([]) ->
[].

% **************************************************

% **************************************************
% Copied from http://stackoverflow.com/a/4762387/4162959
% **************************************************

maxBy(F, L) ->
element(
2,
lists:max([ {F(X), X} || X <- L])
).

% **************************************************

% **************************************************
% Copied from https://panduwana.wordpress.com/2010/04/21/combination-in-erlang/
% **************************************************

combos(L) ->
lists:foldl(
fun(K, Acc) -> Acc++(combos(K, L)) end,
[[]],
lists:seq(1, length(L))
).

combos(1, L) ->
[[X] || X <- L];
combos(K, L) when K == length(L) ->
[L];
combos(K, [H|T]) ->
[[H | Subcombos]
|| Subcombos <- combos(K-1, T)]
++ (combos(K, T)).

% **************************************************

```

Output naive:

```
[3,4,5]
[0,4,6,9,13,15]

```

Output patience:

```
[2,4,5]
[0,2,6,9,11,15]

```

## Go

Patience sorting

```package main

import (
"fmt"
"sort"
)

type Node struct {
val int
back *Node
}

func lis (n []int) (result []int) {
var pileTops []*Node
// sort into piles
for _, x := range n {
j := sort.Search(len(pileTops), func (i int) bool { return pileTops[i].val >= x })
node := &Node{ x, nil }
if j != 0 { node.back = pileTops[j-1] }
if j != len(pileTops) {
pileTops[j] = node
} else {
pileTops = append(pileTops, node)
}
}

if len(pileTops) == 0 { return []int{} }
for node := pileTops[len(pileTops)-1]; node != nil; node = node.back {
result = append(result, node.val)
}
// reverse
for i := 0; i < len(result)/2; i++ {
result[i], result[len(result)-i-1] = result[len(result)-i-1], result[i]
}
return
}

func main() {
for _, d := range [][]int{{3, 2, 6, 4, 5, 1},
{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}} {
fmt.Printf("an L.I.S. of %v is %v\n", d, lis(d))
}
}
```

{{out}}

```an L.I.S. of [3 2 6 4 5 1] is [2 4 5]
an L.I.S. of [0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15] is [0 2 6 9 11 15]
```

### Naive implementation

```import Data.Ord          ( comparing )
import Data.List         ( maximumBy, subsequences )
import Data.List.Ordered ( isSorted, nub )

lis :: Ord a => [a] -> [a]
lis = maximumBy (comparing length) . map nub  . filter isSorted . subsequences
--    longest                    <-- unique <-- increasing    <-- all

main = do
print \$ lis [3,2,6,4,5,1]
print \$ lis [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]
print \$ lis [1,1,1,1]
```

{{out}}

```[2,4,5]
[0,2,6,9,11,15]
[1]
```

### Patience sorting

```{-# LANGUAGE FlexibleContexts, UnicodeSyntax #-}

module Main (main, lis) where

import Control.Monad.ST  ( ST, runST )
import Control.Monad     ( (>>=), (=<<), foldM )
import Data.Array.ST     ( Ix,  STArray, readArray, writeArray, newArray )
import Data.Array.MArray ( MArray )

infix 4 ≡

(≡) :: Eq α ⇒ α → α → Bool
(≡) = (==)

(∘) = (.)

lis ∷ Ord α ⇒ [α] → [α]
lis xs = runST \$ do
let lxs = length xs
pileTops ← newSTArray (min 1 lxs , lxs) []
i        ← foldM (stack pileTops) 0 xs
readArray pileTops i >>= return ∘ reverse

stack ∷ (Integral ι, Ord ε, Ix ι, MArray α [ε] μ)
⇒ α ι [ε] → ι → ε → μ ι
stack piles i x = do
j ← bsearch piles x i
writeArray piles j ∘ (x:) =<< if j ≡ 1 then return []
else readArray piles (j-1)
return \$ if j ≡ i+1 then i+1 else i

bsearch ∷ (Integral ι, Ord ε, Ix ι, MArray α [ε] μ)
⇒ α ι [ε] → ε → ι → μ ι
bsearch piles x = go 1
where go lo hi | lo > hi   = return lo
| otherwise =
do (y:_) ← readArray piles mid
if y < x then go (succ mid) hi
else go lo (pred mid)

where mid = (lo + hi) `div` 2

newSTArray ∷ Ix ι ⇒ (ι,ι) → ε → ST σ (STArray σ ι ε)
newSTArray = newArray

main ∷ IO ()
main = do
print \$ lis [3, 2, 6, 4, 5, 1]
print \$ lis [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
print \$ lis [1, 1, 1, 1]
```

{{out}}

```[2,4,5]
[0,2,6,9,11,15]
[1]
```

The following works in both languages:

```procedure main(A)
every writes((!lis(A)||" ") | "\n")
end

procedure lis(A)
r := [A[1]] | fail
every (put(pt := [], [v := !A]), p := !pt) do
if put(p, p[-1] < v) then r := (*p > *r, p)
else p[-1] := (p[-2] < v)
return r
end
```

Sample runs:

```
->lis 3 2 6 4 5 1
3 4 5
->lis 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
0 4 6 9 11 15
->

```

## J

These examples are simple enough for brute force to be reasonable:

```increasing=: (-: /:~)@#~"1 #:@i.@^~&2@#
longestinc=: ] #~ [: (#~ ([: (= >./) +/"1)) #:@I.@increasing
```

In other words: consider all 2^n bitmasks of length n, and select those which strictly select increasing sequences. Find the length of the longest of these and use the masks of that length to select from the original sequence.

Example use:

```
longestinc 3,2,6,4,5,1
2 4 5
3 4 5
longestinc 0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15
0 2 6 9 11 15
0 2 6 9 13 15
0 4 6 9 11 15
0 4 6 9 13 15
```

## Java

A solution based on patience sorting, except that it is not necessary to keep the whole pile, only the top (in solitaire, bottom) of the pile, along with pointers from each "card" to the top of its "previous" pile.

```import java.util.*;

public class LIS {
public static <E extends Comparable<? super E>> List<E> lis(List<E> n) {
List<Node<E>> pileTops = new ArrayList<Node<E>>();
// sort into piles
for (E x : n) {
Node<E> node = new Node<E>();
node.value = x;
int i = Collections.binarySearch(pileTops, node);
if (i < 0) i = ~i;
if (i != 0)
node.pointer = pileTops.get(i-1);
if (i != pileTops.size())
pileTops.set(i, node);
else
}
// extract LIS from nodes
List<E> result = new ArrayList<E>();
for (Node<E> node = pileTops.size() == 0 ? null : pileTops.get(pileTops.size()-1);
node != null; node = node.pointer)
Collections.reverse(result);
return result;
}

private static class Node<E extends Comparable<? super E>> implements Comparable<Node<E>> {
public E value;
public Node<E> pointer;
public int compareTo(Node<E> y) { return value.compareTo(y.value); }
}

public static void main(String[] args) {
List<Integer> d = Arrays.asList(3,2,6,4,5,1);
System.out.printf("an L.I.S. of %s is %s\n", d, lis(d));
d = Arrays.asList(0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15);
System.out.printf("an L.I.S. of %s is %s\n", d, lis(d));
}
}
```

{{out}}

```an L.I.S. of [3, 2, 6, 4, 5, 1] is [2, 4, 5]
an L.I.S. of [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] is [0, 2, 6, 9, 11, 15]
```

## JavaScript

```function getLis(input) {
if (input.length === 0) {
return [];
}

var lisLenPerIndex = [];
let max = { index: 0, length: 1 };

for (var i = 0; i < input.length; i++) {
lisLenPerIndex[i] = 1;
for (var j = i - 1; j >= 0; j--) {
if (input[i] > input[j] && lisLenPerIndex[j] >= lisLenPerIndex[i]) {
var length = lisLenPerIndex[i] = lisLenPerIndex[j] + 1;
if (length > max.length) {
max = { index: i, length };
}
}
}
}

var lis = [input[max.index]];
for (var i = max.index; i >= 0 && max.length !== 0; i--) {
if (input[max.index] > input[i] && lisLenPerIndex[i] === max.length - 1) {
lis.unshift(input[i]);
max.length--;
}
}

return lis;
}

console.log(getLongestIncreasingSubsequence([0, 7, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]));
console.log(getLongestIncreasingSubsequence([3, 2, 6, 4, 5, 1]));

```

{{out}}

```
[ 0, 2, 6, 9, 11, 15 ]
[ 2, 4, 5 ]

```

## jq

{{works with|jq|1.4}} Use the patience sorting method to find a longest (strictly) increasing subsequence.

'''Generic functions:'''

Recent versions of jq have functions that obviate the need for the two generic functions defined in this subsection.

```def until(cond; update):
def _until:
if cond then . else (update | _until) end;
try _until catch if .== "break" then empty else . end;

# binary search for insertion point
def bsearch(target):
. as \$in
| [0, length-1] # [low, high]
| until(.[0] > .[1];
.[0] as \$low | .[1] as \$high
| (\$low + (\$high - \$low) / 2 | floor) as \$mid
| if \$in[\$mid] >= target
then .[1] = \$mid - 1
else .[0] = \$mid + 1
end )
| .[0];
```

'''lis:'''

```def lis:

# Helper function:
# given a stream, produce an array of the items in reverse order:
def reverse(stream): reduce stream as \$i ([]; [\$i] + .);

# put the items into increasing piles using the structure:
# NODE = {"val": value, "back": NODE}
reduce .[] as \$x
( []; # array of NODE
# binary search for the appropriate pile
(map(.val) | bsearch(\$x)) as \$i
| setpath([\$i];
{"val": \$x,
"back": (if \$i > 0 then .[\$i-1] else null end) })
)
| .[length - 1]
| reverse( recurse(.back) | .val ) ;
```

'''Examples:'''

```( [3,2,6,4,5,1],
[0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]
) | lis
```

{{out}}

```\$ jq -c -n -f lis.jq
[2,4,5]
[0,2,6,9,11,15]

```

## Julia

{{works with|Julia|0.6}}

```
function lis(arr::Vector)
if length(arr) == 0 return copy(arr) end
L = Vector{typeof(arr)}(length(arr))
L[1] = [arr[1]]

for i in 2:length(arr)
nextL = []
for j in 1:i
if arr[j] < arr[i] && length(L[j]) ≥ length(nextL)
nextL = L[j]
end
end
L[i] = vcat(nextL, arr[i])
end

return L[indmax(length.(L))]
end

@show lis([3, 2, 6, 4, 5, 1])
@show lis([0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15])
```

{{out}}

```lis([3, 2, 6, 4, 5, 1]) = [2, 4, 5]
lis([0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]) = [0, 2, 6, 9, 11, 15]
```

## Kotlin

Uses the algorithm in the Wikipedia L.I.S. article:

```// version 1.1.0

fun longestIncreasingSubsequence(x: IntArray): IntArray =
when (x.size) {
0    -> IntArray(0)
1    -> x
else -> {
val n = x.size
val p = IntArray(n)
val m = IntArray(n + 1)
var len = 0
for (i in 0 until n) {
var lo = 1
var hi = len
while (lo <= hi) {
val mid = Math.ceil((lo + hi) / 2.0).toInt()
if (x[m[mid]] < x[i]) lo = mid + 1
else hi = mid - 1
}
val newLen = lo
p[i] = m[newLen - 1]
m[newLen] = i
if (newLen > len) len = newLen
}
val s = IntArray(len)
var k = m[len]
for (i in len - 1 downTo 0) {
s[i] = x[k]
k = p[k]
}
s
}
}

fun main(args: Array<String>) {
val lists = listOf(
intArrayOf(3, 2, 6, 4, 5, 1),
intArrayOf(0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15)
)
lists.forEach { println(longestIncreasingSubsequence(it).asList()) }
}
```

{{out}}

```
[2, 4, 5]
[0, 2, 6, 9, 11, 15]

```

## Lua

```function buildLIS(seq)
local piles = { { {table.remove(seq, 1), nil} } }
while #seq>0 do
local x=table.remove(seq, 1)
for j=1,#piles do
if piles[j][#piles[j]][1]>x then
table.insert(piles[j], {x, (piles[j-1] and #piles[j-1])})
break
elseif j==#piles then
table.insert(piles, {{x, #piles[j]}})
end
end
end
local t={}
table.insert(t, piles[#piles][1][1])
local p=piles[#piles][1][2]
for i=#piles-1,1,-1 do
table.insert(t, piles[i][p][1])
p=piles[i][p][2]
end
table.sort(t)
print(unpack(t))
end

buildLIS({3,2,6,4,5,1})
buildLIS({0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15})

```

{{out}}

```2   4   5
0   2   6   9   11  15

```

## M2000 Interpreter

### Using Stack objects in an array

stack:=stackitem(L(i)), ! stack(L(j)) returns a refence to a new stack object, with the first item on L(i) (which is a reference to stack object) and merge using ! the copy of L(j) stack.

```
Module LIS_example {
Function LIS {
LD=Stack.Size-1
dim L(0 to LD)
For i=0 to LD : Read V: L(i):=Stack:=V:next
M=1
M1=LD
for i=LD-1 to 0
for j=LD to i+1
if stackitem(L(i))<stackitem(L(j)) then
if len(L(i))<=len(L(j)) then L(i) =stack:=stackitem(L(i)), ! stack(L(j))
end if
next
if len(L(i))>=M then M1=i:M=Len(L(i))
next
=L(M1)
}
Const seq\$="sequence", subseq\$="Longest increasing subsequence"
Document doc\$
Disp(seq\$, Stack:=3,2,6,4,5,1)
Disp(subseq\$, Lis(3,2,6,4,5,1))
Disp(seq\$, Stack:=0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15)
Disp(subseq\$, LIS(0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15))
Print #-2,Doc\$
Clipboard Doc\$

Sub Disp(title\$, m)
local n=each(m), s\$
while n
s\$+=", "+str\$(stackitem(n),"")
end while
s\$=trim\$(mid\$(s\$, 2))
Doc\$=title\$+": "+s\$+{
}
End Sub
}
LIS_example

```

### Using arrays in an array

```
Module LIS_example {
Function LIS {
LD=Stack.Size-1
dim L(0 to LD)
For i=0 to LD : Read V: L(i):=(V,):next
M=1
M1=LD
for i=LD-1 to 0
for j=LD to i+1
if Array(L(i))<Array(L(j)) then
' 	you can use either is the same
'	if len(L(i))<=len(L(j)) then L(i)=Cons((Array(L(i)),), L(j))
if len(L(i))<=len(L(j)) then L(i)=(Array(L(i)),): Append L(i), L(j)
end if
next
if len(L(i))>=M then M1=i:M=Len(L(i))
next
=L(M1)
}
Const seq\$="sequence", subseq\$="Longest increasing subsequence"
Document doc\$
Disp(seq\$, (3,2,6,4,5,1))
Disp(subseq\$, LIS(3,2,6,4,5,1))
Disp(seq\$, (0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15))
Disp(subseq\$, LIS(0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15))
Print #-2,Doc\$
Clipboard Doc\$

Sub Disp(title\$, m)
local n=each(m), s\$
while n
s\$+=", "+str\$(Array(n),"")
end while
s\$=trim\$(mid\$(s\$, 2))
Doc\$=title\$+": "+s\$+{
}
End Sub
}
LIS_example

```

{{out}}

```sequence: 3, 2, 6, 4, 5, 1
Longest increasing subsequence: 3, 4, 5
sequence: 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
Longest increasing subsequence: 0, 2, 6, 9, 11, 15
```