1058 Intermediate

1058-longest-increasing-subseq — Longest Increasing Subsequence

Functional Programming

Tutorial

The Problem

The longest increasing subsequence (LIS) finds the longest subsequence of a sequence where elements are strictly increasing. It appears in scheduling (job sequencing by deadline), genomics (conserved gene segments), and card games (patience sorting, which inspired the O(n log n) algorithm).

The naive O(n²) DP can be improved to O(n log n) using patience sorting — the key insight being that you maintain a list of "piles" whose tops are sorted, enabling binary search.

🎯 Learning Outcomes

• Implement the O(n²) LIS DP

• Implement the O(n log n) patience-sorting algorithm using binary search

• Use Rust's binary_search for the patience sort step

• Understand why patience sort works via the pigeonhole principle

• Connect LIS to the O(n log n) bounds on comparison-based sorting

Code Example

#![allow(clippy::all)]
// 1058: Longest Increasing Subsequence — O(n log n) Patience Sorting

// Approach 1: O(n^2) DP
fn lis_dp(arr: &[i32]) -> usize {
    if arr.is_empty() {
        return 0;
    }
    let n = arr.len();
    let mut dp = vec![1usize; n];
    for i in 1..n {
        for j in 0..i {
            if arr[j] < arr[i] {
                dp[i] = dp[i].max(dp[j] + 1);
            }
        }
    }
    *dp.iter().max().unwrap()
}

// Approach 2: O(n log n) patience sorting with binary search
fn lis_patience(arr: &[i32]) -> usize {
    let mut tails: Vec<i32> = Vec::new();
    for &x in arr {
        match tails.binary_search(&x) {
            Ok(pos) => tails[pos] = x,
            Err(pos) => {
                if pos == tails.len() {
                    tails.push(x);
                } else {
                    tails[pos] = x;
                }
            }
        }
    }
    tails.len()
}

// Approach 3: Iterator-based with fold
fn lis_fold(arr: &[i32]) -> usize {
    arr.iter()
        .fold(Vec::new(), |mut tails: Vec<i32>, &x| {
            match tails.binary_search(&x) {
                Ok(pos) => tails[pos] = x,
                Err(pos) => {
                    if pos == tails.len() {
                        tails.push(x);
                    } else {
                        tails[pos] = x;
                    }
                }
            }
            tails
        })
        .len()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_lis_dp() {
        assert_eq!(lis_dp(&[10, 9, 2, 5, 3, 7, 101, 18]), 4);
        assert_eq!(lis_dp(&[0, 1, 0, 3, 2, 3]), 4);
        assert_eq!(lis_dp(&[7, 7, 7, 7]), 1);
    }

    #[test]
    fn test_lis_patience() {
        assert_eq!(lis_patience(&[10, 9, 2, 5, 3, 7, 101, 18]), 4);
        assert_eq!(lis_patience(&[0, 1, 0, 3, 2, 3]), 4);
        assert_eq!(lis_patience(&[7, 7, 7, 7]), 1);
    }

    #[test]
    fn test_lis_fold() {
        assert_eq!(lis_fold(&[10, 9, 2, 5, 3, 7, 101, 18]), 4);
        assert_eq!(lis_fold(&[0, 1, 0, 3, 2, 3]), 4);
    }
}

(* 1058: Longest Increasing Subsequence — O(n log n) Patience Sorting *)

(* Approach 1: O(n^2) DP *)
let lis_dp arr =
  let n = Array.length arr in
  if n = 0 then 0
  else begin
    let dp = Array.make n 1 in
    for i = 1 to n - 1 do
      for j = 0 to i - 1 do
        if arr.(j) < arr.(i) then
          dp.(i) <- max dp.(i) (dp.(j) + 1)
      done
    done;
    Array.fold_left max 0 dp
  end

(* Approach 2: O(n log n) patience sorting with binary search *)
let lis_patience arr =
  let n = Array.length arr in
  if n = 0 then 0
  else begin
    let tails = Array.make n 0 in
    let len = ref 0 in
    for i = 0 to n - 1 do
      (* Binary search for position *)
      let lo = ref 0 and hi = ref !len in
      while !lo < !hi do
        let mid = (!lo + !hi) / 2 in
        if tails.(mid) < arr.(i) then lo := mid + 1
        else hi := mid
      done;
      tails.(!lo) <- arr.(i);
      if !lo = !len then incr len
    done;
    !len
  end

(* Approach 3: Functional with lists *)
let lis_functional arr =
  let binary_search tails x len =
    let lo = ref 0 and hi = ref len in
    while !lo < !hi do
      let mid = (!lo + !hi) / 2 in
      if tails.(mid) < x then lo := mid + 1
      else hi := mid
    done;
    !lo
  in
  let n = Array.length arr in
  if n = 0 then 0
  else begin
    let tails = Array.make n 0 in
    let len = ref 0 in
    Array.iter (fun x ->
      let pos = binary_search tails x !len in
      tails.(pos) <- x;
      if pos = !len then incr len
    ) arr;
    !len
  end

let () =
  assert (lis_dp [|10; 9; 2; 5; 3; 7; 101; 18|] = 4);
  assert (lis_dp [|0; 1; 0; 3; 2; 3|] = 4);
  assert (lis_dp [|7; 7; 7; 7|] = 1);

  assert (lis_patience [|10; 9; 2; 5; 3; 7; 101; 18|] = 4);
  assert (lis_patience [|0; 1; 0; 3; 2; 3|] = 4);
  assert (lis_patience [|7; 7; 7; 7|] = 1);

  assert (lis_functional [|10; 9; 2; 5; 3; 7; 101; 18|] = 4);

  Printf.printf "✓ All tests passed\n"

Key Differences

**binary_search API**: Rust's binary_search returns Ok(pos) for exact matches and Err(pos) for insertion points; the patience algorithm needs Err(pos) which maps to a lower-bound bisection.

In-place vs Vec growth: Rust's tails grows dynamically with push; OCaml pre-allocates an array of the input length.

Reconstruction: Both require a separate dp array to reconstruct the actual LIS (not just its length); the tails array does not directly encode the subsequence.

Stability: The patience sort variant is stable and used in Python's timsort merge decision algorithm.

OCaml Approach

let lis_patience arr =
  let tails = Array.make (Array.length arr) 0 in
  let len = ref 0 in
  Array.iter (fun x ->
    (* Binary search for insertion position *)
    let lo = ref 0 and hi = ref !len in
    while !lo < !hi do
      let mid = (!lo + !hi) / 2 in
      if tails.(mid) < x then lo := mid + 1 else hi := mid
    done;
    tails.(!lo) <- x;
    if !lo = !len then incr len
  ) arr;
  !len

The algorithm is identical. The binary search for the lower bound is the same in both languages.

Full Source

#![allow(clippy::all)]
// 1058: Longest Increasing Subsequence — O(n log n) Patience Sorting

// Approach 1: O(n^2) DP
fn lis_dp(arr: &[i32]) -> usize {
    if arr.is_empty() {
        return 0;
    }
    let n = arr.len();
    let mut dp = vec![1usize; n];
    for i in 1..n {
        for j in 0..i {
            if arr[j] < arr[i] {
                dp[i] = dp[i].max(dp[j] + 1);
            }
        }
    }
    *dp.iter().max().unwrap()
}

// Approach 2: O(n log n) patience sorting with binary search
fn lis_patience(arr: &[i32]) -> usize {
    let mut tails: Vec<i32> = Vec::new();
    for &x in arr {
        match tails.binary_search(&x) {
            Ok(pos) => tails[pos] = x,
            Err(pos) => {
                if pos == tails.len() {
                    tails.push(x);
                } else {
                    tails[pos] = x;
                }
            }
        }
    }
    tails.len()
}

// Approach 3: Iterator-based with fold
fn lis_fold(arr: &[i32]) -> usize {
    arr.iter()
        .fold(Vec::new(), |mut tails: Vec<i32>, &x| {
            match tails.binary_search(&x) {
                Ok(pos) => tails[pos] = x,
                Err(pos) => {
                    if pos == tails.len() {
                        tails.push(x);
                    } else {
                        tails[pos] = x;
                    }
                }
            }
            tails
        })
        .len()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_lis_dp() {
        assert_eq!(lis_dp(&[10, 9, 2, 5, 3, 7, 101, 18]), 4);
        assert_eq!(lis_dp(&[0, 1, 0, 3, 2, 3]), 4);
        assert_eq!(lis_dp(&[7, 7, 7, 7]), 1);
    }

    #[test]
    fn test_lis_patience() {
        assert_eq!(lis_patience(&[10, 9, 2, 5, 3, 7, 101, 18]), 4);
        assert_eq!(lis_patience(&[0, 1, 0, 3, 2, 3]), 4);
        assert_eq!(lis_patience(&[7, 7, 7, 7]), 1);
    }

    #[test]
    fn test_lis_fold() {
        assert_eq!(lis_fold(&[10, 9, 2, 5, 3, 7, 101, 18]), 4);
        assert_eq!(lis_fold(&[0, 1, 0, 3, 2, 3]), 4);
    }
}

(* 1058: Longest Increasing Subsequence — O(n log n) Patience Sorting *)

(* Approach 1: O(n^2) DP *)
let lis_dp arr =
  let n = Array.length arr in
  if n = 0 then 0
  else begin
    let dp = Array.make n 1 in
    for i = 1 to n - 1 do
      for j = 0 to i - 1 do
        if arr.(j) < arr.(i) then
          dp.(i) <- max dp.(i) (dp.(j) + 1)
      done
    done;
    Array.fold_left max 0 dp
  end

(* Approach 2: O(n log n) patience sorting with binary search *)
let lis_patience arr =
  let n = Array.length arr in
  if n = 0 then 0
  else begin
    let tails = Array.make n 0 in
    let len = ref 0 in
    for i = 0 to n - 1 do
      (* Binary search for position *)
      let lo = ref 0 and hi = ref !len in
      while !lo < !hi do
        let mid = (!lo + !hi) / 2 in
        if tails.(mid) < arr.(i) then lo := mid + 1
        else hi := mid
      done;
      tails.(!lo) <- arr.(i);
      if !lo = !len then incr len
    done;
    !len
  end

(* Approach 3: Functional with lists *)
let lis_functional arr =
  let binary_search tails x len =
    let lo = ref 0 and hi = ref len in
    while !lo < !hi do
      let mid = (!lo + !hi) / 2 in
      if tails.(mid) < x then lo := mid + 1
      else hi := mid
    done;
    !lo
  in
  let n = Array.length arr in
  if n = 0 then 0
  else begin
    let tails = Array.make n 0 in
    let len = ref 0 in
    Array.iter (fun x ->
      let pos = binary_search tails x !len in
      tails.(pos) <- x;
      if pos = !len then incr len
    ) arr;
    !len
  end

let () =
  assert (lis_dp [|10; 9; 2; 5; 3; 7; 101; 18|] = 4);
  assert (lis_dp [|0; 1; 0; 3; 2; 3|] = 4);
  assert (lis_dp [|7; 7; 7; 7|] = 1);

  assert (lis_patience [|10; 9; 2; 5; 3; 7; 101; 18|] = 4);
  assert (lis_patience [|0; 1; 0; 3; 2; 3|] = 4);
  assert (lis_patience [|7; 7; 7; 7|] = 1);

  assert (lis_functional [|10; 9; 2; 5; 3; 7; 101; 18|] = 4);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_lis_dp() {
        assert_eq!(lis_dp(&[10, 9, 2, 5, 3, 7, 101, 18]), 4);
        assert_eq!(lis_dp(&[0, 1, 0, 3, 2, 3]), 4);
        assert_eq!(lis_dp(&[7, 7, 7, 7]), 1);
    }

    #[test]
    fn test_lis_patience() {
        assert_eq!(lis_patience(&[10, 9, 2, 5, 3, 7, 101, 18]), 4);
        assert_eq!(lis_patience(&[0, 1, 0, 3, 2, 3]), 4);
        assert_eq!(lis_patience(&[7, 7, 7, 7]), 1);
    }

    #[test]
    fn test_lis_fold() {
        assert_eq!(lis_fold(&[10, 9, 2, 5, 3, 7, 101, 18]), 4);
        assert_eq!(lis_fold(&[0, 1, 0, 3, 2, 3]), 4);
    }
}

Deep Comparison

Longest Increasing Subsequence — Comparison

Core Insight

The patience sorting algorithm maintains a sorted tails array. For each element, binary search finds its position — either extending the longest subsequence or replacing an element to keep tails minimal. This achieves O(n log n) vs the naive O(n^2) DP.

OCaml Approach

• Manual binary search with ref cells for lo/hi

• Array.fold_left max 0 for finding maximum in O(n^2) version

• Array.iter with side effects for the patience sort

• No built-in binary search on arrays

Rust Approach

• slice::binary_search returns Ok(pos) or Err(insertion_point) — perfect for patience sort

• Vec as dynamic tails array with push and indexing

• Iterator fold for a functional patience sort variant

• Pattern matching on binary_search result is elegant

Comparison Table

Aspect	OCaml	Rust
Binary search	Manual implementation	`slice::binary_search()` built-in
Search result	Returns index	`Result<Ok(pos), Err(pos)>`
Dynamic array	Fixed `Array` + length counter	`Vec` with `push`
Fold variant	Less natural (array mutation)	Clean `fold` over iterator
Max finding	`Array.fold_left max 0`	`iter().max().unwrap()`

Exercises

Modify lis_patience to also reconstruct the actual LIS elements, not just the length.

Implement the longest non-decreasing subsequence (≤ instead of <) by changing the binary search comparison.

Write lis_count(arr: &[i32]) -> usize that counts the number of distinct LIS sequences of maximum length.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust