789 Intermediate

789-longest-increasing-subsequence — Longest Increasing Subsequence

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "789-longest-increasing-subsequence — Longest Increasing Subsequence" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. The Longest Increasing Subsequence (LIS) problem finds the longest subsequence of a sequence in which all elements are in sorted increasing order. Key difference from OCaml: 1. **Binary search**: Rust's `Vec::binary_search` returns `Ok(pos)` for exact match and `Err(pos)` for insertion point — exactly what LIS needs; OCaml uses `Array.binary_search` from third

Tutorial

The Problem

The Longest Increasing Subsequence (LIS) problem finds the longest subsequence of a sequence in which all elements are in sorted increasing order. It appears in patience sorting (used in the solitaire card game and by Timsort), scheduling theory, and bioinformatics. The naive O(n²) DP is classic; the O(n log n) solution using binary search and "patience sorting" is a key algorithmic insight showing that binary search applies to DP optimization.

🎯 Learning Outcomes

• Implement the O(n²) DP solution: dp[i] = LIS length ending at index i

• Implement the O(n log n) binary search solution using a tails array

• Understand the tails invariant: tails[i] is the smallest tail element of any increasing subsequence of length i+1

• Apply binary_search to maintain the tails array

• Reconstruct the actual LIS by storing predecessor indices

Code Example

#![allow(clippy::all)]
//! # Longest Increasing Subsequence

pub fn lis(arr: &[i32]) -> usize {
    if arr.is_empty() {
        return 0;
    }
    let mut dp = vec![1; arr.len()];
    for i in 1..arr.len() {
        for j in 0..i {
            if arr[j] < arr[i] {
                dp[i] = dp[i].max(dp[j] + 1);
            }
        }
    }
    *dp.iter().max().unwrap()
}

pub fn lis_binary_search(arr: &[i32]) -> usize {
    let mut tails = Vec::new();
    for &x in arr {
        match tails.binary_search(&x) {
            Ok(_) => {}
            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() {
        assert_eq!(lis(&[10, 9, 2, 5, 3, 7, 101, 18]), 4);
    }
    #[test]
    fn test_binary() {
        assert_eq!(lis_binary_search(&[10, 9, 2, 5, 3, 7, 101, 18]), 4);
    }
    #[test]
    fn test_empty() {
        assert_eq!(lis(&[]), 0);
    }
}

(* LIS — patience sorting O(n log n)
   OCaml style: functional binary search, Array for tails *)

(* Binary search: find leftmost position in [0, hi) where tails.(pos) >= x *)
let lower_bound tails hi x =
  let rec go lo hi =
    if lo >= hi then lo
    else
      let mid = lo + (hi - lo) / 2 in
      if tails.(mid) < x then go (mid + 1) hi
      else go lo mid
  in
  go 0 hi

let lis 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
    Array.iter (fun x ->
      let pos = lower_bound tails !len x in
      tails.(pos) <- x;
      if pos = !len then incr len
    ) arr;
    !len
  end

(* Reconstruct the actual LIS (not just length) *)
let lis_reconstruct arr =
  let n = Array.length arr in
  if n = 0 then [||]
  else begin
    let tails = Array.make n 0 in
    let pred  = Array.make n (-1) in  (* predecessor index *)
    let idx   = Array.make n 0 in     (* index in arr for each tails slot *)
    let len   = ref 0 in
    for i = 0 to n - 1 do
      let x   = arr.(i) in
      let pos = lower_bound tails !len x in
      tails.(pos) <- x;
      idx.(pos)   <- i;
      pred.(i)    <- if pos > 0 then idx.(pos - 1) else -1;
      if pos = !len then incr len
    done;
    (* Walk back via pred *)
    let result = Array.make !len 0 in
    let k = ref (idx.(!len - 1)) in
    for j = !len - 1 downto 0 do
      result.(j) <- arr.(!k);
      k := pred.(!k)
    done;
    result
  end

let () =
  let arr = [| 10; 9; 2; 5; 3; 7; 101; 18 |] in
  Printf.printf "Array: ";
  Array.iter (fun x -> Printf.printf "%d " x) arr;
  print_newline ();
  Printf.printf "LIS length: %d\n" (lis arr);
  let seq = lis_reconstruct arr in
  Printf.printf "LIS sequence: ";
  Array.iter (fun x -> Printf.printf "%d " x) seq;
  print_newline ();

  (* Edge cases *)
  Printf.printf "Empty LIS: %d\n" (lis [||]);
  Printf.printf "All same [3;3;3]: %d\n" (lis [|3;3;3|]);
  Printf.printf "Sorted [1;2;3;4;5]: %d\n" (lis [|1;2;3;4;5|]);
  Printf.printf "Reverse [5;4;3;2;1]: %d\n" (lis [|5;4;3;2;1|])

Key Differences

Binary search: Rust's Vec::binary_search returns Ok(pos) for exact match and Err(pos) for insertion point — exactly what LIS needs; OCaml uses Array.binary_search from third-party libraries.

Algorithm clarity: The tails invariant is subtle; both languages benefit from a comment explaining why this works despite tails not being the actual LIS.

Reconstruction: Both languages use an O(n²) predecessor array for reconstruction; it cannot be inferred from tails alone.

Timsort connection: Python's timsort uses the patience sorting / LIS insight to identify already-sorted runs; Rust's std sort uses a similar technique.

OCaml Approach

OCaml implements the O(n²) version functionally with Array.init n (fun i -> ...) and the O(n log n) version with a mutable tails array and binary search via Array.blit. OCaml's standard library includes Array.blit for efficient element shifts. The patience sorting metaphor maps naturally: each pile is a tails slot, and placing a card uses binary search to find the leftmost pile that accepts it.

Full Source

#![allow(clippy::all)]
//! # Longest Increasing Subsequence

pub fn lis(arr: &[i32]) -> usize {
    if arr.is_empty() {
        return 0;
    }
    let mut dp = vec![1; arr.len()];
    for i in 1..arr.len() {
        for j in 0..i {
            if arr[j] < arr[i] {
                dp[i] = dp[i].max(dp[j] + 1);
            }
        }
    }
    *dp.iter().max().unwrap()
}

pub fn lis_binary_search(arr: &[i32]) -> usize {
    let mut tails = Vec::new();
    for &x in arr {
        match tails.binary_search(&x) {
            Ok(_) => {}
            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() {
        assert_eq!(lis(&[10, 9, 2, 5, 3, 7, 101, 18]), 4);
    }
    #[test]
    fn test_binary() {
        assert_eq!(lis_binary_search(&[10, 9, 2, 5, 3, 7, 101, 18]), 4);
    }
    #[test]
    fn test_empty() {
        assert_eq!(lis(&[]), 0);
    }
}

(* LIS — patience sorting O(n log n)
   OCaml style: functional binary search, Array for tails *)

(* Binary search: find leftmost position in [0, hi) where tails.(pos) >= x *)
let lower_bound tails hi x =
  let rec go lo hi =
    if lo >= hi then lo
    else
      let mid = lo + (hi - lo) / 2 in
      if tails.(mid) < x then go (mid + 1) hi
      else go lo mid
  in
  go 0 hi

let lis 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
    Array.iter (fun x ->
      let pos = lower_bound tails !len x in
      tails.(pos) <- x;
      if pos = !len then incr len
    ) arr;
    !len
  end

(* Reconstruct the actual LIS (not just length) *)
let lis_reconstruct arr =
  let n = Array.length arr in
  if n = 0 then [||]
  else begin
    let tails = Array.make n 0 in
    let pred  = Array.make n (-1) in  (* predecessor index *)
    let idx   = Array.make n 0 in     (* index in arr for each tails slot *)
    let len   = ref 0 in
    for i = 0 to n - 1 do
      let x   = arr.(i) in
      let pos = lower_bound tails !len x in
      tails.(pos) <- x;
      idx.(pos)   <- i;
      pred.(i)    <- if pos > 0 then idx.(pos - 1) else -1;
      if pos = !len then incr len
    done;
    (* Walk back via pred *)
    let result = Array.make !len 0 in
    let k = ref (idx.(!len - 1)) in
    for j = !len - 1 downto 0 do
      result.(j) <- arr.(!k);
      k := pred.(!k)
    done;
    result
  end

let () =
  let arr = [| 10; 9; 2; 5; 3; 7; 101; 18 |] in
  Printf.printf "Array: ";
  Array.iter (fun x -> Printf.printf "%d " x) arr;
  print_newline ();
  Printf.printf "LIS length: %d\n" (lis arr);
  let seq = lis_reconstruct arr in
  Printf.printf "LIS sequence: ";
  Array.iter (fun x -> Printf.printf "%d " x) seq;
  print_newline ();

  (* Edge cases *)
  Printf.printf "Empty LIS: %d\n" (lis [||]);
  Printf.printf "All same [3;3;3]: %d\n" (lis [|3;3;3|]);
  Printf.printf "Sorted [1;2;3;4;5]: %d\n" (lis [|1;2;3;4;5|]);
  Printf.printf "Reverse [5;4;3;2;1]: %d\n" (lis [|5;4;3;2;1|])

✓ Tests Rust test suite

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

    #[test]
    fn test_lis() {
        assert_eq!(lis(&[10, 9, 2, 5, 3, 7, 101, 18]), 4);
    }
    #[test]
    fn test_binary() {
        assert_eq!(lis_binary_search(&[10, 9, 2, 5, 3, 7, 101, 18]), 4);
    }
    #[test]
    fn test_empty() {
        assert_eq!(lis(&[]), 0);
    }
}

Deep Comparison

OCaml vs Rust: Longest Increasing Subsequence

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement lis_reconstruct(arr: &[i32]) -> Vec<i32> that returns the actual LIS (not just its length) by storing predecessor indices during the O(n²) DP.

Modify lis_binary_search to handle non-strictly-increasing (allowing equal elements) by changing < to <= in the binary search.

Use LIS to count the minimum number of strictly decreasing subsequences needed to partition a sequence (Dilworth's theorem: equals LIS length).

Open Source Repos

functional-rust

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

Rust