Longest Increasing Subsequence (LIS) Problem in DSA

Nidhi Sharma
14h
2.8k
0
0

Article

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:

Elements do not need to be continuous
Order must remain the same

Example

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

Valid subsequences:

[10, 9]
[2, 5, 7]
[10, 2, 7]

What is an Increasing Subsequence?

An increasing subsequence is a subsequence where:

Each next element is greater than the previous one

Example

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

[2, 5, 7] is increasing
[10, 9] is NOT increasing

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

Huge number of subsequences
Time complexity becomes exponential

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)

For each element, find the LIS ending at that element
Use previously calculated results

We create a DP array where:

dp[i] = length of LIS ending at index i

Step-by-Step DP Explanation

Steps:

Initialize all dp[i] = 1 (every element is an LIS of length 1)
For each element i, check all previous elements j < i
If nums[i] > nums[j], update:
- dp[i] = max(dp[i], dp[j] + 1)
The answer is the maximum value in dp

Dry Run Example

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

Index	Value	dp value
0	10	1
1	9	1
2	2	1
3	5	2
4	3	2
5	7	3

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)

Maintain a temporary array that stores smallest possible ending value
Use binary search to place elements

This approach improves performance significantly.

Time and Space Complexity

Dynamic Programming Approach

Time Complexity: O(n²)
Space Complexity: O(n)

Optimized Approach

Time Complexity: O(n log n)
Space Complexity: O(n)

Edge Cases to Consider

Empty array
All elements are same
Strictly decreasing array

Always test these cases.

Common Interview Variations

Print the actual LIS
Count number of LIS
Longest decreasing subsequence
LIS with constraints

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.