Understanding Algorithms (Advanced Dynamic Programming), Part 27: Longest Increasing Subsequence (LIS).

Longest Increasing Subsequence (LIS) finds the longest strictly increasing sequence within an array while keeping the original order. It can be solved using dynamic programming in O(n²) or optimized with binary search to O(n log n).

The Longest Increasing Subsequence (LIS) problem focuses on finding the maximum-length subsequence of a given sequence such that the elements are in strictly increasing order. Like LCS, the elements do not need to be contiguous. What matters is relative ordering. This problem appears simple on the surface but introduces powerful ideas about optimization over sequences.

Formally, given an array of numbers A[0…n−1], the goal is to find the longest subsequence A[i₁], A[i₂], …, A[iₖ] such that i₁ < i₂ < … < iₖ and A[i₁] < A[i₂] < … < A[iₖ].

A brute-force approach would examine every subsequence and check whether it is increasing. Since there are 2ⁿ possible subsequences, this method is computationally infeasible even for moderately sized inputs.

The problem naturally fits Dynamic Programming because it exhibits optimal substructure. The LIS ending at any position depends on LIS values computed for earlier positions. Each prefix contributes information needed for larger prefixes.

The classic DP formulation defines dp[i] = length of the Longest Increasing Subsequence ending exactly at index i.

Each element starts with a base value of 1, because any single element is itself an increasing subsequence of length one.

For every index i, all previous indices j < i are checked. If A[j] < A[i], then A[i] can extend the subsequence ending at j dp[i] = max(dp[i], dp[j] + 1).

After filling dp for all indices, the final answer is simply max(dp[i]).

This approach runs in O(n²) time and uses O(n) space. While quadratic, it is often acceptable for inputs up to a few thousand elements and clearly illustrates the core DP logic: build answers incrementally by reusing smaller results.

However, LIS also has a more optimized solution using binary search, achieving O(n log n) time. This version does not directly compute dp[i] for every index. Instead, it maintains an auxiliary array, commonly called tails.

The idea is to track the smallest possible tail value for increasing subsequences of different lengths.

tails[k] stores the minimum ending value of any increasing subsequence of length k+1 found so far.

For each element x in the input, if x is larger than all elements in tails, it is appended, extending the longest subsequence.

Otherwise, x replaces the smallest element in tails that is greater than or equal to x (found using binary search).

This replacement does not represent an actual subsequence, but it preserves the possibility of building longer sequences later. Smaller tail values are always better because they leave more room for future growth.

The length of the tails array at the end gives the length of the LIS.

Although this optimized method does not directly store the actual sequence, it efficiently computes the length. With additional bookkeeping, the sequence itself can also be reconstructed.

Conceptually, this approach shifts the problem from explicit DP states to maintaining best candidates for subsequence endings. It demonstrates how combining greedy intuition with binary search can dramatically reduce complexity while preserving correctness.

The LIS problem appears in scheduling, pattern recognition, version control systems, stock analysis, and sequence modeling. Any scenario involving trend detection or ordered progression maps naturally to LIS. It also forms the foundation for more advanced problems such as longest bitonic subsequence and multidimensional LIS.

Algorithmically, LIS teaches how local comparisons accumulate into global structure. It shows two contrasting strategies: a straightforward quadratic DP that exposes the recurrence clearly, and a logarithmic optimization that trades transparency for performance.

More importantly, LIS reinforces a core idea in algorithm design: many sequence optimization problems can be solved by defining precise states, understanding transitions, and then searching for ways to compress those states without losing essential information. This pattern appears repeatedly in advanced Dynamic Programming and competitive programming tasks, where performance constraints demand both correctness and efficiency.

class LongestIncreasingSubsequence:
    def __init__(self):
        """
        Initializes Longest Increasing Subsequence.

        What LIS means:
        - Find the longest subsequence that is strictly increasing.
        - Elements must keep original order.
        - They do NOT need to be contiguous.

        Core idea:
        - Dynamic Programming.
        - Each position depends on all previous positions.
        """

        pass

    # --------------------------------------------------
    # LIS USING DYNAMIC PROGRAMMING (O(n^2))
    # --------------------------------------------------
    def lis(self, nums):
        """
        Computes length of Longest Increasing Subsequence.

        Strategy:
        - dp[i] stores LIS ending at index i.

        Rule:
        - If nums[j] < nums[i], nums[i] can extend subsequence at j.
        """

        if not nums:
            return 0

        n = len(nums)

        # Every element is at least an LIS of length 1
        dp = [1] * n

        # Build solution left to right
        for i in range(n):
            for j in range(i):

                # Valid increasing condition
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp)

# --------------------------------------------------
# EXAMPLE USAGE
# --------------------------------------------------

nums = [10, 9, 2, 5, 3, 7, 101, 18]

lis_solver = LongestIncreasingSubsequence()

length = lis_solver.lis(nums)

print("Length of LIS:", length)