Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence does not need to be contiguous.

Function signature

func LengthOfLIS(nums []int) int

Examples

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The LIS is [2,3,7,101].

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:

Input: nums = [7,7,7,7]
Output: 1

Constraints

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

Hints

1. O(n^2) DP works for small inputs.
2. The optimized approach keeps a tails array and uses binary search.
3. tails[i] is the smallest possible tail of any increasing subsequence of length i+1.

Notes

• You only need the length, not the actual subsequence.
• Binary search on tails gives O(n log n).