Faangprep Logo
Log inStart free
Browse curriculum

Longest Increasing Subsequence

The longest increasing subsequence (LIS) problem asks for the length of the longest strictly increasing subsequence of an integer array.

READY

0

1

2

3

4

5

nums

10
9
2
5
3
7

LIS

1
1
1
1
1
1

 

Initialize DP array with 1s. Each element ends an LIS of length 1 by default.

Next

Checking LIS ending at index 0 (Value: 10)

Array

Intuition

Imagine you are jumping across stepping stones in a river, but you can only jump to a stone that is higher than the one you are currently on. You want to make the maximum number of jumps.

Concept

Dynamic Programming (O(N²)):

Let dp[i] be the length of the longest increasing subsequence ending at index i. To calculate dp[i], we look at all previous indices j < i. If nums[j] < nums[i], we can extend the subsequence ending at j. So, dp[i] = max(dp[i], dp[j] + 1).

How it Works

Algorithm:

  1. Initialize dp array of size N with 1s.
  2. Iterate i from 1 to N-1.
  3. Inner loop j from 0 to i-1.
  4. If nums[i] > nums[j], update dp[i] = max(dp[i], dp[j] + 1).
  5. The answer is the maximum value in the entire dp array.

Step-by-Step Breakdown

Visualizing the 1D DP Array:

  • Base State: Every element is an LIS of length 1 (itself).
  • Extension: When we find a smaller previous element, we 'extend' its LIS.
  • Result: The longest LIS isn't necessarily at the last index; it's the max of all dp values.

When to Use

Applications:

  • Analyzing trends (stock market).
  • Optimization problems where order matters.
  • Layering or stacking problems (e.g., Russian Doll Envelopes).

When NOT to Use

  • Contiguous Subarray: For contiguous subarrays, use Kadane's or Sliding Window.
  • Arbitrary Order: If original order doesn't matter, just Sort and remove duplicates.

How to Identify

"Find longest sequence... strictly increasing... original order".

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Longest Common Subsequence

Next

Edit Distance

Frequently Asked Questions

How does LIS work?

LIS finds the longest chain of numbers in a sequence that strictly increases from left to right.

Standard DP vs Patience Sorting?

The standard DP approach is O(n^2). The optimized version using Binary Search (Patience Sorting) is O(n log n).

Max Increasing Subsequence Sum?

This is a variation where instead of the longest count, you seek the subset with the highest aggregate sum.