1058: Longest Increasing Subsequence

Difficulty: Intermediate-Advanced Category: Dynamic Programming / Binary Search Concept: Find the length of the longest strictly increasing subsequence using patience sorting Key Insight: Maintain a `tails` array where `tails[i]` is the smallest tail element of all increasing subsequences of length `i+1` — binary search determines where each new element fits, achieving O(n log n).

// 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()
}

fn main() {
    let arr = [10, 9, 2, 5, 3, 7, 101, 18];
    println!("LIS of {:?} = {}", arr, lis_patience(&arr));
    println!("LIS (fold) = {}", lis_fold(&arr));
}

#[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"

📊 Detailed 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()`