Back to Study Material Data Structures and Algorithms

Longest Increasing Subsequence

The longest increasing subsequence (LIS) problem asks: given an array of n integers, find the length of the longest subsequence in which each element is st...

Longest Increasing Subsequence

O(n^2) DP Approach

The longest increasing subsequence (LIS) problem asks: given an array of n integers, find the length of the longest subsequence in which each element is strictly greater than the previous one. Unlike subarray problems, the subsequence elements do not need to be contiguous.

The O(n^2) dynamic programming approach: define dp[i] as the length of the LIS ending at index i. Base case: dp[i] = 1 for all i (each element alone is an increasing subsequence of length 1). Recurrence: for each i, look at all j < i where arr[j] < arr[i]; dp[i] = max(dp[j] + 1) over all such j. The final answer is max(dp[i]) over all i.

A worked example: arr = [10, 9, 2, 5, 3, 7, 101, 18]. dp[0] = 1 (just 10). dp[1] = 1 (9 alone, nothing smaller before it). dp[2] = 1 (2 alone). dp[3] = 2 (5 > 2, dp[2] + 1). dp[4] = 2 (3 > 2, dp[2] + 1). dp[5] = 3 (7 > 5 and 7 > 3, max dp is dp[3] = 2, so dp[5] = 3). dp[6] = 4 (101 > 7, dp[5] + 1). dp[7] = 4 (18 > 7, dp[5] + 1). Answer = 4, corresponding to 2, 3, 7, 18 or 2, 5, 7, 18.

Time complexity is O(n^2) for the double loop; space is O(n) for the dp array. Reconstructing the actual subsequence requires a parent array tracking which j gave the optimal dp[i], then backtracking from the index with maximum dp value.

Interview tip: Start with the O(n^2) solution to establish correctness clearly, then mention the O(n log n) approach for large inputs. Jumping directly to the patience sorting trick without first explaining the simpler solution often leaves interviewers uncertain whether you understand the problem fundamentally.

O(n log n) Patience Sorting Approach

The O(n log n) algorithm for LIS uses a technique inspired by the card game patience sorting. Maintain a list called tails, where tails[i] is the smallest tail element among all increasing subsequences of length i+1 seen so far. The key insight: a smaller tail element for a given length is always preferable because it gives more room for future elements to extend the subsequence.

Algorithm: for each element x in the array, binary search tails for the leftmost position where tails[pos] >= x. If no such position exists (x is larger than all tails), append x to tails (LIS length increases by one). Otherwise, replace tails[pos] with x (keep the tail small). The length of the LIS is the final length of tails.

A worked example: arr = [3, 1, 8, 2, 5]. Process 3: tails = [3]. Process 1: 1 < 3, replace tails[0]: tails = [1]. Process 8: 8 > 1, append: tails = [1, 8]. Process 2: 2 is between 1 and 8, replace tails[1]: tails = [1, 2]. Process 5: 5 > 2, append: tails = [1, 2, 5]. LIS length = 3, corresponding to 1, 2, 5.

Note: tails itself is not necessarily a valid LIS. It only encodes lengths. To reconstruct the actual LIS, you need an additional parent array updated during the binary search, which adds O(n) space.

Time complexity: O(n log n) — n elements, each requiring an O(log n) binary search on tails. Space: O(n) for tails and the parent array.

Interview tip: This algorithm requires lower_bound (the leftmost position where tails[pos] >= x). Accidentally using upper_bound produces the longest non-decreasing subsequence instead of strictly increasing. State this boundary choice explicitly when explaining the algorithm.

Variants: LDS, LNDS, and Bitonic Subsequences

The LIS framework extends naturally to several related problems encountered in competitive programming and interviews. The longest decreasing subsequence (LDS) of an array is simply the LIS of the negated array. Negate all elements, run LIS, and the result is the LDS length.

The longest non-decreasing subsequence (LNDS) allows equal consecutive elements. Change the binary search from lower_bound (leftmost >= x) to upper_bound (leftmost > x). This small change allows equal elements to extend the current tail rather than replacing it.

The longest bitonic subsequence first increases then decreases. Compute LIS_from_left[i] = length of LIS ending at index i (using standard LIS). Compute LIS_from_right[i] = length of LIS starting at index i (equivalent to LDS ending at i, computed by running LIS on the reversed array). The longest bitonic subsequence through index i has length LIS_from_left[i] + LIS_from_right[i] - 1 (subtract 1 to avoid double-counting index i). The answer is the maximum over all i.

A related problem: find the minimum number of elements to remove to make an array sorted. This equals n minus the LIS length, because the elements you keep form an increasing subsequence, so maximizing what you keep minimizes what you remove.

The patience sorting interpretation also explains the connection to a combinatorial result: the minimum number of decreasing subsequences needed to partition the entire array equals the LIS length (Dilworth's theorem). This provides a dual problem: partitioning into decreasing subsequences vs. finding the LIS.

Interview tip: Knowing that LIS length equals the minimum number of chains needed in Dilworth's theorem is a distinctive insight that very few candidates mention. It signals deep mathematical understanding and is worth stating if the interviewer seems interested in theoretical connections.