Find the Longest Increasing Subsequence (LIS) efficiently.

Basic DP: dp[i] = LIS ending at index i. For each i, dp[i] = 1 + max(dp[j]) for j < i where arr[j] < arr[i]. O(n^2) time. Optimized O(n log n): maintain array of smallest tail elements for LIS of each length. For each element, binary search to find position (extends existing or replaces tail). Length of array is LIS length. Reconstruction requires additional bookkeeping.