Introduction

The Longest Increasing Subsequence (LIS) problem is a widely asked DSA interview question, particularly in the Dynamic Programming category. It is often asked because it checks your ability to think about optimization, state transitions, and problem breakdown.

In simple words, this problem asks you to find the longest sequence of numbers that keeps increasing, while keeping their original order.

This article explains LIS in simple, step-by-step language, from basic concepts to interview-level solutions.

What is a Subsequence?

A subsequence is formed by selecting some elements from an array without changing their order.

Important points:

Example

Array: [10, 9, 2, 5, 3, 7]

Valid subsequences:

What is an Increasing Subsequence?

An increasing subsequence is a subsequence where:

Example

From [10, 9, 2, 5, 3, 7]:

What is the Longest Increasing Subsequence Problem?

You are given an array of integers. Your task is to find the length of the longest increasing subsequence.

Example

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

Explanation

One longest increasing subsequence is:

[2, 5, 7, 101]

So the length is 4.

Why Brute Force Approach is Not Practical

In the brute-force approach, we try all possible subsequences and check which ones are increasing.

Problems with Brute Force

This approach is not acceptable in interviews.

Dynamic Programming Approach (Most Important)

The most common and expected solution uses Dynamic Programming (DP).

DP Idea (Very Simple)

We create a DP array where:

Step-by-Step DP Explanation

Steps:

  1. Initialize all dp[i] = 1 (every element is an LIS of length 1)

  2. For each element i, check all previous elements j < i

  3. If nums[i] > nums[j], update:

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

  4. The answer is the maximum value in dp

Dry Run Example

Array: [10, 9, 2, 5, 3, 7]

IndexValuedp value
0101
191
221
352
432
573

Final Answer = 3

Code Implementation (Dynamic Programming)

C++ Code

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    int ans = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }
    return ans;
}

Java Code

public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);

    int ans = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        ans = Math.max(ans, dp[i]);
    }
    return ans;
}

Python Code

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)

Optimized LIS Approach (Binary Search – O(n log n))

For advanced interviews, an optimized approach is expected.

Key Idea (Intuition)

This approach improves performance significantly.

Time and Space Complexity

Dynamic Programming Approach

Optimized Approach

Edge Cases to Consider

Always test these cases.

Common Interview Variations

Summary

The Longest Increasing Subsequence (LIS) problem is a core dynamic programming question that teaches how to build solutions using previous results. Starting with a simple DP approach helps understand the logic, while the optimized binary search method improves performance. Mastering LIS is extremely important for interviews, as it builds a strong foundation for many advanced dynamic programming problems.