Longest Increasing Subsequence (LIS)

In the previous lesson, we studied the Longest Common Subsequence (LCS) and learned how Dynamic Programming helps us compare two sequences efficiently.

Now we move to another classic and very important problem: Longest Increasing Subsequence (LIS).

This problem focuses on a single sequence and teaches how to make optimal decisions over time.

What Is a Subsequence?

A subsequence is formed by deleting some elements from a sequence without changing the order of the remaining elements.

Example:

Sequence: [3, 10, 2, 1, 20]
One subsequence: [3, 10, 20]

The elements are not adjacent, but the order is preserved.

What Is Longest Increasing Subsequence?

The Longest Increasing Subsequence is the longest subsequence where the elements are strictly increasing.

Example:

Input: [10, 9, 2, 5, 3, 7, 101, 18]

One LIS is: [2, 5, 7, 101]

The answer is the length: 4

Why LIS Is Challenging

At each position, we must decide whether to include the current element in the subsequence.

A greedy choice does not always work, because a locally good decision may block better choices later.

This makes LIS a perfect candidate for Dynamic Programming.

Defining the Subproblem

Let dp[i] represent the length of the LIS ending at index i.

Initially, each element is an LIS of length 1 by itself.

LIS Recurrence Relation

For every pair of indices i and j where j < i:

If nums[i] > nums[j]:

dp[i] = max(dp[i], dp[j] + 1)

This means: we extend the increasing sequence ending at j.

Dynamic Programming Implementation

def lengthOfLIS(nums):
    n = len(nums)
    dp = [1] * n

    for i in range(n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

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

Each dp[i] stores the best increasing sequence ending exactly at i.

Understanding the Logic

We scan the array from left to right.

For each element, we look back at all previous elements and check whether we can extend an increasing sequence.

The final answer is the maximum value in the dp array.

Time and Space Complexity

Time Complexity: O(n²)

Space Complexity: O(n)

Although faster solutions exist, this DP approach is the most intuitive and interview-friendly.

Real-World Applications

LIS appears in:

• Stock price trend analysis
• Career growth tracking
• Versioned software updates
• Pattern recognition problems

Mini Practice

Think carefully:

• Why does dp start with all values set to 1?
• What happens if numbers are all decreasing?

Exercises

Quick Quiz

Longest Increasing Subsequence helps build strong intuition for sequence-based Dynamic Programming.

In the next lesson, we will solve the 0/1 Knapsack Problem, one of the most famous DP problems ever.