206. Longest Increasing Subsequence

Given an array of n integers, find the length of its longest strictly increasing subsequence.

Input: The first line contains an integer n. The second line contains n space-separated integers, the array. Output: Print a single integer - the length of the longest strictly increasing subsequence.

1 <= n <= 10^5

The answer is the MAXIMUM across the ENTIRE dp array, not just its last entry - the longest increasing subsequence doesn't have to end at the array's final element, an easy detail to overlook.

Find the length of the longest strictly increasing subsequence within an array. Brute force: Try every possible subsequence (2^n of them) and check which are increasing, taking the longest - this is exponential, impractical for n up to 10^5. Optimised: The O(n²) DP checks every pair (i,j) once, reusing already-computed dp[j] values rather than re-deriving subsequences from scratch - and an even faster O(n log n) approach maintains a list of 'smallest tail value achievable for each subsequence length', using binary search to find where each new element fits, avoiding the full O(n²) pairwise comparison entirely.

Recursively decide, for each element, whether to include it in the subsequence or skip it, only allowing an inclusion if it's strictly greater than the last included element, and take the maximum length achieved over all valid choices. This directly checks every one of the 2^n possible subsequences for the increasing property, guaranteeing correctness, but is exponential and infeasible for anything but very small arrays. Time: O(2^n) Space: O(n)

Maintain an array 'tails' where tails[k] holds the smallest possible tail value of any increasing subsequence of length k+1 found so far; for each new number, binary search tails for the first entry greater than or equal to it and overwrite that position (or append if it's larger than everything currently in tails). The final length of tails is the LIS length, since keeping the smallest possible tail for each subsequence length maximizes the chance of extending it later; using binary search to place each element turns the O(n) inner scan of the DP approach into an O(log n) lookup, which is essential given n can be up to 10^5. Time: O(n log n) Space: O(n)

Define dp[i] as the length of the longest increasing subsequence that ends exactly at index i, computed as 1 plus the maximum dp[j] over all j < i where array[j] < array[i] (or just 1 if no such j exists). Filling this array left to right and taking its maximum value avoids re-exploring overlapping subsequence choices from scratch, cutting the exponential brute force down to a quadratic number of comparisons. Time: O(n^2) Space: O(n)

1. dp[i] = length of the longest increasing subsequence ENDING exactly at index i. 2. For each i, look at every earlier index j with arr[j] < arr[i], and take dp[i] = max(dp[i], dp[j] + 1). 3. The answer is the MAXIMUM value anywhere in the dp array, not necessarily dp[n-1].

Time: O(n²) for the straightforward DP; O(n log n) with the tails-array-plus-binary-search optimization. Space: O(n), for the dp array (or the tails array in the optimized approach).

Test n = 1 (answer 1), a strictly decreasing array (answer 1), and n at the upper bound of 10^5, which requires the O(n log n) approach rather than O(n^2).

Be ready to present BOTH the O(n²) DP and the O(n log n) optimized approach - interviewers frequently ask for the faster one as a follow-up, given how iconic this problem is.