Longest Increasing Subsequence

Given an integer array, return the length of the longest strictly increasing subsequence. An O(n^2) DP works but can be optimized.

Function signature

func LengthOfLIS(nums []int) int

Inputs / outputs

• nums: array of integers.
• Return: length of the LIS.

Example

nums = [10,9,2,5,3,7,101,18]
One LIS is [2,3,7,101]
Output: 4

Constraints

• 1 <= len(nums) <= 100_000

Core idea (near-solution)

Patience sorting: maintain tails, where tails[i] is the smallest possible tail of any increasing subsequence of length i+1.

Invariant: tails is increasing and correctly represents minimal tails for each length.

Algorithm (step-by-step)

1. Initialize empty tails.
2. For each x in nums:
   • Find the first index i where tails[i] >= x (lower bound).
   • If none, append x; else replace tails[i] = x.
3. Return len(tails).

Correctness sketch

• Invariant: tails is increasing and correctly represents minimal tails for each length.
• The DP state represents the optimal answer for a prefix or subproblem.
• The recurrence uses only previously solved states, preserving correctness.
• The final DP value (or max over DP) is the correct answer.

Trace (hand walkthrough)

Example input:
nums = [10,9,2,5,3,7,101,18]
One LIS is [2,3,7,101]
Output: 4

Walk:
- tails: [10] -> [9] -> [2] -> [2,5] -> [2,3] -> [2,3,7] -> [2,3,7,101] -> [2,3,7,18]
- length = 4

Pitfalls to avoid

• Treating tails as the actual subsequence (it is not).
• Using > instead of >= in lower bound (breaks strictness).

Complexity

• Time: O(n log n).
• Extra space: O(n).

Implementation notes (Go)

• Implement binary search manually to avoid extra imports.