Longest Increasing Subsequence — Go Coding Problem
Difficulty: medium | Category: dynamic-programming
Problem Description
Given an integer array `nums`, return the length of the longest **strictly increasing** subsequence. A subsequence is a sequence derived from the array by deleting some (or no) elements without changing the order of remaining elements. Hint: O(n log n) solution — maintain a `tails` array. For each number, binary search for the first element in `tails` that is ≥ the number and replace it, or append if larger than all.
Examples
Example 1
Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: [2, 3, 7, 101]
Example 2
Input: nums = [0, 1, 0, 3, 2, 3]
Output: 4
Example 3
Input: nums = [7, 7, 7, 7, 7]
Output: 1