LIS Theory

1. O(n²) DP

dp[i] = 1
for i in 0..n-1:
  for j in 0..i-1:
    if a[j] < a[i]:
      dp[i] = max(dp[i], dp[j] + 1)

2. O(n log n) Patience Sorting

piles = []
for x in a:
  place x on leftmost pile with top >= x (binary search)
length = len(piles)

Piles store minimal tail for subsequences of each length; they are non-decreasing.

3. Reconstruction (O(n log n) approach)

Maintain predecessor indices and an array of pile ends (indices), then backtrack from last pile.

4. Variants

• Non-decreasing variant: use > instead of >= in binary search condition.
• 2D envelopes: sort by one dimension, LIS on second with tie rules.
• Circular sequences: duplicate array and constrain start window.