Introduction

Longest Increasing Subsequence (LIS) is one of the most important Dynamic Programming interview questions.

You are given:

nums[]

Goal:

Find the length of the longest strictly increasing subsequence.

A subsequence:

Find the length of the longest strictly increasing subsequence.

Example

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

Output:

4

Explanation:

LIS = [2,3,7,101]
Length = 4

Key Observation

For every element:

Try extending all previous increasing subsequences.

Recurrence:

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

where:
j < i and nums[j] < nums[i]

Approach 1 : Memoization

Explanation

For each index:

  1. Take current number.
  2. Compare with previous number.
  3. Extend increasing sequence.
  4. Store results.
  5. Reuse computations.

Approach 2 : Tabulation

Explanation

State:

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

Transition:

If nums[j] < nums[i]

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

Dry Run

Input:

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

DP Array:

[1,1,1,2,2,3,4,4]

Answer:

4

Subsequence:

[2,3,7,101]

Approach 3 : Binary Search Optimization

Explanation

Instead of checking all previous elements:

Maintain a tails array.

Idea:

tails[i] = Smallest possible tail for an increasing subsequence of length i+1.

Use Binary Search to place elements.

Practice

Complexity Analysis

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

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

Binary Search Optimization
Time Complexity: O(n log n)
Space Complexity: O(n)

Why This Problem is Important

  • Sequence Dynamic Programming
  • Binary Search Optimization
  • State Transitions
  • Longest Subsequence Problems
  • Foundation for Advanced LIS Variants

Common Beginner Mistakes

  • Confusing subsequence with subarray
  • Using <= instead of <
  • Incorrect binary search implementation
  • Wrong DP state definition
  • Forgetting strict increasing condition

Interview Tip

Always explain:

dp[i] = Length of LIS ending at i

Then mention:

Optimized solution uses Binary Search with tails array.

This often impresses interviewers.

Related Questions

  • Number of LIS
  • Russian Doll Envelopes
  • Longest Bitonic Subsequence
  • Largest Divisible Subset
  • Maximum Length Pair Chain

Final Takeaway

Longest Increasing Subsequence is one of the most important Dynamic Programming problems.

It teaches:

  • Sequence DP
  • State Design
  • Binary Search Optimization
  • Subsequence Problems
  • Advanced DP Thinking

Mastering LIS provides the foundation for many advanced sequence and optimization interview questions.