dp[i] = 1 + max(dp[j]) para todo j < i onde arr[j] < arr[i]

Array: [10, 9, 2, 5, 3, 7, 101, 18]

DP (O(n²)):
  i=0: dp[0]=1  (10)
  i=1: dp[1]=1  (9)
  i=2: dp[2]=1  (2)
  i=3: dp[3]=2  (2,5)
  i=4: dp[4]=2  (2,3)
  i=5: dp[5]=3  (2,3,7) ou (2,5,7)
  i=6: dp[6]=4  (2,3,7,101)
  i=7: dp[7]=4  (2,3,7,18)

Patience Sorting (O(n log n)):
  Processa 10: tails = [10]
  Processa 9:  tails = [9]         (substitui 10)
  Processa 2:  tails = [2]         (substitui 9)
  Processa 5:  tails = [2, 5]      (estende)
  Processa 3:  tails = [2, 3]      (substitui 5)
  Processa 7:  tails = [2, 3, 7]   (estende)
  Processa 101: tails = [2, 3, 7, 101] (estende)
  Processa 18: tails = [2, 3, 7, 18]   (substitui 101)

  LIS comprimento = 4

const std = @import("std");
const Allocator = std.mem.Allocator;

/// LIS com DP — O(n²) tempo, O(n) espaço.
/// Retorna o comprimento e a subsequência reconstruída.
pub fn lisDP(
    allocator: Allocator,
    arr: []const i32,
) !struct { comprimento: usize, subsequencia: []i32 } {
    const n = arr.len;
    if (n == 0) return .{ .comprimento = 0, .subsequencia = &.{} };

    const dp = try allocator.alloc(usize, n);
    defer allocator.free(dp);
    const prev = try allocator.alloc(i32, n);
    defer allocator.free(prev);

    @memset(dp, 1);
    @memset(prev, -1);

    var max_len: usize = 1;
    var max_idx: usize = 0;

    for (1..n) |i| {
        for (0..i) |j| {
            if (arr[j] < arr[i] and dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                prev[i] = @intCast(j);
            }
        }
        if (dp[i] > max_len) {
            max_len = dp[i];
            max_idx = i;
        }
    }

    // Reconstrói
    var resultado = try allocator.alloc(i32, max_len);
    var idx: usize = max_len;
    var cur: i32 = @intCast(max_idx);
    while (cur >= 0) {
        idx -= 1;
        resultado[idx] = arr[@intCast(cur)];
        cur = prev[@intCast(cur)];
    }

    return .{ .comprimento = max_len, .subsequencia = resultado };
}

/// LIS com busca binária — O(n log n) tempo, O(n) espaço.
pub fn lisBinario(allocator: Allocator, arr: []const i32) !usize {
    if (arr.len == 0) return 0;

    var tails = std.ArrayList(i32).init(allocator);
    defer tails.deinit();

    for (arr) |x| {
        // Busca binária: menor posição onde tails[pos] >= x
        var lo: usize = 0;
        var hi: usize = tails.items.len;
        while (lo < hi) {
            const mid = lo + (hi - lo) / 2;
            if (tails.items[mid] < x) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }

        if (lo == tails.items.len) {
            try tails.append(x);
        } else {
            tails.items[lo] = x;
        }
    }

    return tails.items.len;
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    const arr = [_]i32{ 10, 9, 2, 5, 3, 7, 101, 18 };

    try stdout.print("Array: ", .{});
    for (arr) |x| try stdout.print("{d} ", .{x});
    try stdout.print("\n", .{});

    // Versão O(n²) com reconstrução
    const resultado = try lisDP(allocator, &arr);
    defer allocator.free(resultado.subsequencia);

    try stdout.print("LIS comprimento: {d}\n", .{resultado.comprimento});
    try stdout.print("LIS: ", .{});
    for (resultado.subsequencia) |x| try stdout.print("{d} ", .{x});
    try stdout.print("\n", .{});

    // Versão O(n log n)
    const comp = try lisBinario(allocator, &arr);
    try stdout.print("LIS (busca binária): {d}\n", .{comp});
}