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

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

;Ref:

[http://www.youtube.com/watch?v=4fQJGoeW5VE Dynamic Programming #1: Longest Increasing Subsequence] on YouTube

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(n²) 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.

=={{header|Déjà Vu}}== {{trans|Python}}

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:

• Naive version{{trans|Haskell}}
• 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]

Haskell

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]

=={{header|Icon}} and {{header|Unicon}}==

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
                pileTops.add(node);
        }
	// 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)
	    result.add(node.value);
	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