Hints — p58 Longest Increasing Subsequence

Hint 1. Subsequence ≠ substring. Elements need not be contiguous. Try all 2ⁿ subsequences and you get a trivial exponential brute force.

Hint 2. O(n²) DP: dp[i] = LIS ending exactly at index i. For each i, scan all j < i with nums[j] < nums[i] and take dp[i] = max(dp[j]) + 1. Answer = max(dp).

Hint 3. Can we go O(n log n)? Maintain a sorted array tails where tails[k] = the smallest possible tail value of any increasing subseq of length k+1 seen so far. For each new x, binary-search for where it fits.

Hint 4. For strictly-increasing LIS: pos = bisect_left(tails, x). If pos == len(tails), append (we extended the LIS). Else, overwrite tails[pos] = x (we now have a smaller tail for that length). Answer = len(tails).

Hint 5. tails is NOT the actual LIS — its values can drift. To reconstruct the LIS, store predecessor pointers per index alongside the patience-sort scan.

If stuck: see solution.py.