Longest Increasing Subsequence in DSA Python - Deep Dive

Overview - Longest Increasing Subsequence

What is it?

The Longest Increasing Subsequence (LIS) is a sequence of numbers taken from a list where each number is bigger than the one before it, and the sequence is as long as possible. It does not have to be made of consecutive numbers from the original list, but the order must stay the same. For example, in the list [3, 10, 2, 1, 20], the LIS is [3, 10, 20]. Finding the LIS helps us understand patterns and trends in data.

Why it matters

Without the concept of LIS, it would be hard to find the longest pattern of growth or improvement in data, like stock prices or student scores. This would make it difficult to analyze progress or predict future trends. LIS helps in many real-world problems like genetics, computer graphics, and scheduling by identifying the longest chain of increasing events or values.

Where it fits

Before learning LIS, you should understand arrays or lists and basic loops. After LIS, you can learn about dynamic programming, binary search optimization, and other sequence problems like Longest Common Subsequence or Maximum Sum Increasing Subsequence.

Mental Model

Core Idea

The Longest Increasing Subsequence is the longest chain you can build by picking numbers in order, each bigger than the last.

Think of it like...

Imagine climbing a staircase where each step is higher than the previous one, but you can skip some steps if you want. The longest path you can climb without going down is like the LIS.

Input: [3, 10, 2, 1, 20]

Possible subsequences:
  [3, 10, 20]  (length 3)
  [2, 20]      (length 2)
  [1, 20]      (length 2)

Longest Increasing Subsequence:
  3 -> 10 -> 20 -> null

Build-Up - 7 Steps

1

Foundation

Understanding Subsequences

Concept: Learn what a subsequence is and how it differs from a substring or subarray.

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, from [3, 10, 2, 1, 20], [3, 2, 20] is a subsequence but not a substring because the elements are not consecutive. This idea is key to LIS because we look for increasing subsequences, not necessarily consecutive.

Result

You can identify subsequences by skipping elements but keeping order.

Understanding subsequences helps you see that LIS is about order, not closeness, which opens up many possibilities for solutions.

2

Foundation

What Makes a Sequence Increasing?

Concept: Define what it means for a sequence to be strictly increasing.

A sequence is strictly increasing if every next number is bigger than the previous one. For example, [3, 10, 20] is strictly increasing because 3 < 10 < 20. But [3, 10, 10] is not strictly increasing because 10 is not greater than 10. This strictness is important for LIS.

Result

You can check if a sequence is increasing by comparing each pair of neighbors.

Knowing the strict rule prevents confusion and helps in writing correct checks during LIS calculation.

3

Intermediate

Brute Force Approach to LIS

🤔Before reading on: do you think checking all subsequences is practical for large lists? Commit to yes or no.

Concept: Explore the simplest method by checking all subsequences to find the longest increasing one.

The brute force way is to generate every subsequence of the list and check if it is increasing. Then pick the longest one. For example, for [3, 10, 2], subsequences include [3], [10], [2], [3,10], [3,2], [10,2], [3,10,2]. Among these, [3,10] is increasing and longest. But this method is very slow because the number of subsequences grows exponentially.

Result

Brute force finds the correct LIS but is too slow for big lists.

Understanding brute force shows why we need smarter methods to handle bigger data efficiently.

4

Intermediate

Dynamic Programming Solution

🤔Before reading on: do you think storing results of smaller problems can speed up LIS calculation? Commit to yes or no.

Concept: Use dynamic programming to build solutions for LIS by remembering results of smaller parts.

We create an array dp where dp[i] stores the length of the LIS ending at index i. For each element, we look back at all previous elements smaller than it and update dp[i] = max(dp[i], dp[j] + 1). Finally, the answer is the maximum value in dp. This method runs in O(n^2) time.

Result

dp array example for [3, 10, 2, 1, 20]: dp = [1, 2, 1, 1, 3], LIS length = 3

Knowing how to break the problem into smaller overlapping parts is key to efficient LIS calculation.

5

Intermediate

Reconstructing the LIS Sequence

Concept: Learn how to find the actual LIS, not just its length.

Along with dp, keep track of the previous index for each element that forms the LIS. After filling dp, find the index with the maximum dp value and follow the chain of previous indices backward to reconstruct the LIS sequence. This helps us see the actual numbers, not just the length.

Result

For [3, 10, 2, 1, 20], reconstructed LIS is [3, 10, 20]

Reconstruction connects abstract lengths to concrete sequences, making LIS results actionable.

6

Advanced

Optimized O(n log n) LIS Algorithm

🤔Before reading on: do you think binary search can help find LIS faster? Commit to yes or no.

Concept: Use a clever method with binary search to speed up LIS calculation.

Maintain an array tails where tails[k] is the smallest possible tail of an increasing subsequence of length k+1. For each number, use binary search to find where it fits in tails and update tails accordingly. The length of tails is the LIS length. This runs in O(n log n) time.

Result

For [3, 10, 2, 1, 20], tails evolve as: [3], [3,10], [2,10], [1,10], [1,20], LIS length = 3

Combining binary search with dynamic ideas drastically improves performance for large inputs.

7

Expert

Handling Equal Elements and Variations

🤔Before reading on: do you think LIS always requires strictly increasing sequences? Commit to yes or no.

Concept: Explore variations like non-decreasing subsequences and how to adapt algorithms.

Sometimes problems ask for longest non-decreasing subsequence where equal elements are allowed. The binary search condition changes from strictly greater to greater or equal. Also, LIS can be adapted for multidimensional data or with constraints. Understanding these nuances helps in real-world problem solving.

Result

For [3, 10, 10, 20], LIS length with non-decreasing rule is 4: [3, 10, 10, 20]

Knowing variations and how to adjust algorithms prepares you for diverse and complex challenges.

Under the Hood

The LIS dynamic programming approach works by building solutions for smaller subproblems and storing them to avoid repeated work. The optimized method uses a tails array to keep track of potential ends of increasing subsequences, and binary search quickly finds where to place new elements. This reduces the problem from checking all subsequences to managing a sorted structure of candidates.

Why designed this way?

Early solutions were brute force and slow. Dynamic programming was introduced to reuse results and avoid recomputation. The binary search optimization was designed to handle large inputs efficiently by exploiting the sorted nature of subsequence tails. Alternatives like segment trees exist but are more complex.

Input array: [3, 10, 2, 1, 20]

DP approach:
Index: 0  1   2  3  4
Value:3 10   2  1 20
DP:   1  2   1  1  3

Optimized tails:
Step 1: tails = [3]
Step 2: tails = [3, 10]
Step 3: tails = [2, 10]
Step 4: tails = [1, 10]
Step 5: tails = [1, 20]

Length of tails = 3

Myth Busters - 4 Common Misconceptions

Quick: Does the LIS have to be made of consecutive elements? Commit to yes or no.

Common Belief: LIS must be made of consecutive elements in the original list.

Reality: LIS is a subsequence, so elements can be skipped as long as order is preserved.

Why it matters: Believing LIS requires consecutive elements limits the solution and leads to incorrect answers.

Quick: Is the LIS always unique? Commit to yes or no.

Common Belief: There is only one unique longest increasing subsequence for any list.

Reality: Multiple different LIS sequences can exist with the same maximum length.

Why it matters: Assuming uniqueness can cause errors when reconstructing or counting LIS.

Quick: Does the LIS algorithm always run in linear time? Commit to yes or no.

Common Belief: LIS can be found in linear time for any input.

Reality: The best known general LIS algorithms run in O(n log n), not linear time.

Why it matters: Expecting linear time can lead to wrong performance assumptions and inefficient code.

Quick: Can LIS include equal elements when strictly increasing is required? Commit to yes or no.

Common Belief: Equal elements can be part of the LIS even if it is strictly increasing.

Reality: Strictly increasing means each next element must be greater, not equal.

Why it matters: Confusing strictness causes incorrect LIS length and sequence.

Expert Zone

1

The tails array in the optimized method does not represent an actual subsequence but helps track potential ends, which is subtle but crucial.

2

Reconstructing the LIS from the optimized method requires extra bookkeeping, as tails alone do not store sequence indices.

3

Handling duplicates and non-strictly increasing sequences requires careful adjustment of binary search conditions.

When NOT to use

LIS algorithms are not suitable when the problem requires consecutive elements (use Longest Increasing Substring instead) or when sequences have complex constraints like weights or multidimensional ordering (use specialized algorithms or segment trees).

Production Patterns

LIS is used in bioinformatics to find gene orderings, in finance to analyze stock trends, and in scheduling to optimize task sequences. Professionals often combine LIS with other algorithms like binary indexed trees or segment trees for enhanced performance.

Connections

Longest Common Subsequence

Both find longest ordered sequences but LCS compares two sequences while LIS works on one.

Understanding LIS helps grasp LCS since both use dynamic programming and subsequence concepts.

Binary Search

The optimized LIS algorithm uses binary search to efficiently place elements.

Mastering binary search unlocks the O(n log n) LIS solution and many other efficient algorithms.

Evolutionary Biology

LIS concepts relate to finding longest chains of increasing traits or gene sequences.

Seeing LIS in biology shows how algorithms model natural growth and adaptation patterns.

Common Pitfalls

#1 Trying to find LIS by checking only consecutive elements.

Wrong approach:

def lis_consecutive(arr):
max_len = 1
curr_len = 1
for i in range(1, len(arr)):
if arr[i] > arr[i-1]:
curr_len += 1
max_len = max(max_len, curr_len)
else:
curr_len = 1
return max_len

Correct approach:

def lis_dp(arr):
n = len(arr)
dp = [1]*n
for i in range(n):
for j in range(i):
if arr[i] > arr[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)

Root cause:

Confusing LIS with longest increasing substring, missing the subsequence property.

#2 Using linear search instead of binary search in the optimized method.

Wrong approach:

def lis_optimized(arr):
tails = []
for x in arr:
pos = 0
while pos < len(tails) and tails[pos] < x:
pos += 1
if pos == len(tails):
tails.append(x)
else:
tails[pos] = x
return len(tails)

Correct approach:

import bisect

def lis_optimized(arr):
tails = []
for x in arr:
pos = bisect.bisect_left(tails, x)
if pos == len(tails):
tails.append(x)
else:
tails[pos] = x
return len(tails)

Root cause:

Not using binary search leads to O(n^2) time, losing optimization benefits.

#3 Allowing equal elements in strictly increasing LIS checks.

Wrong approach:

if arr[i] >= arr[j]:
dp[i] = max(dp[i], dp[j] + 1)

Correct approach:

if arr[i] > arr[j]:
dp[i] = max(dp[i], dp[j] + 1)

Root cause:

Misunderstanding strict inequality requirement for LIS.

Key Takeaways

The Longest Increasing Subsequence finds the longest ordered chain of numbers growing strictly larger, not necessarily consecutive.

Dynamic programming breaks the problem into smaller parts, storing results to avoid repeated work and improve efficiency.

Binary search combined with a tails array optimizes LIS calculation to O(n log n), suitable for large inputs.

Reconstructing the actual LIS sequence requires extra tracking beyond just length calculation.

Understanding LIS variations and common misconceptions prepares you for diverse real-world problems and prevents common errors.

Practice

1. What does the Longest Increasing Subsequence (LIS) problem ask for in a given list of numbers?

easy

A. The longest subsequence where each number is strictly smaller than the previous one

B. The longest subsequence where each number is equal to the previous one

C. The longest subsequence where numbers are in any order

D. The longest subsequence where each number is strictly greater than the previous one

Solution

1. Step 1: Understand the definition of LIS

   The LIS is a subsequence where every next number is strictly greater than the previous one.

2. Step 2: Compare options with the definition

   Only The longest subsequence where each number is strictly greater than the previous one matches the definition of LIS.

3. Final Answer:

   The longest subsequence where each number is strictly greater than the previous one -> Option D

4. Quick Check:

   LIS = strictly increasing subsequence [OK]

Hint: LIS means strictly increasing sequence, not equal or decreasing [OK]

Common Mistakes:

• Confusing LIS with longest equal subsequence
• Thinking LIS allows decreasing numbers
• Assuming LIS means any order

2. Which of the following Python code snippets correctly initializes a list dp to store LIS lengths for each element in nums of length n?

easy

A. dp = [0] * n

B. dp = [1] * n

C. dp = [None] * n

D. dp = []

Solution

1. Step 1: Understand LIS dp initialization

   Each element alone is a subsequence of length 1, so dp should start with 1s.

2. Step 2: Check options for correct initialization

   Only dp = [1] * n initializes dp with 1s for all elements.

3. Final Answer:

   dp = [1] * n -> Option B

4. Quick Check:

   dp initialized with 1 for LIS length [OK]

Hint: Start dp with 1s because each element is LIS of length 1 [OK]

Common Mistakes:

• Initializing dp with zeros instead of ones
• Using None which causes errors in comparisons
• Leaving dp empty

3. What is the output of the following code snippet?

nums = [10, 9, 2, 5, 3, 7, 101, 18]
dp = [1] * len(nums)
for i in range(len(nums)):
    for j in range(i):
        if nums[j] < nums[i]:
            dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))

medium

A. 5

B. 3

C. 4

D. 6

Solution

1. Step 1: Trace dp updates for each element

   Starting dp = [1,1,1,1,1,1,1,1]. Update dp as we find increasing subsequences:
   - i=1: nums[1]=9 < 10? Yes, dp[1]=max(1, dp[0]+1)=2.
   - i=2: nums[2]=2 < 10,9? No update.
   - i=3: nums[3]=5 > 2, dp[3]=max(1, dp[2]+1)=2.
   - i=4: nums[4]=3 > 2, dp[4]=2.
   - i=5: nums[5]=7 > 5,3,2, dp[5]=max(1, dp[3]+1=3, dp[4]+1=3)=3.
   - i=6: nums[6]=101 > all previous, dp[6]=max(1, dp[5]+1=4, dp[1]+1=3, dp[0]+1=2, dp[3]+1=3, dp[4]+1=3) = 5.
   - i=7: nums[7]=18 > 7, dp[7]=max(1, dp[5]+1=4, dp[3]+1=3, dp[4]+1=3) = 4.

2. Step 2: Find max dp value

   Maximum dp value is 5, which is the length of LIS.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Longest Increasing Subsequence length = 5 [OK]

Hint: Use nested loops to update dp with max LIS length [OK]

Common Mistakes:

• Forgetting to update dp[i] with max value
• Mixing up indices i and j
• Printing dp instead of max(dp)

4. The following code is intended to find the length of the LIS but has a bug. What is the bug?

def length_of_lis(nums):
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[j] = max(dp[j], dp[i] + 1)
    return max(dp)

medium

A. dp[j] should be updated as dp[i], not dp[j]

B. The comparison should be nums[j] > nums[i]

C. dp[i] should be updated, not dp[j]

D. The function should return min(dp) instead of max(dp)

Solution

1. Step 1: Identify which dp index to update

   In LIS, dp[i] stores the length of LIS ending at index i. So dp[i] must be updated when nums[i] > nums[j].

2. Step 2: Check the code's update statement

   The code updates dp[j], which is incorrect. It should update dp[i].

3. Final Answer:

   dp[i] should be updated, not dp[j] -> Option C

4. Quick Check:

   Update dp[i] for LIS ending at i [OK]

Hint: Update dp at current index i, not previous j [OK]

Common Mistakes:

• Updating dp[j] instead of dp[i]
• Reversing comparison operators
• Returning min(dp) instead of max(dp)

5. Given the list nums = [3, 10, 2, 1, 20], which of the following is the correct longest increasing subsequence using a binary search optimization approach?

hard

A. [3, 10, 20]

B. [2, 10, 20]

C. [1, 2, 20]

D. [3, 10, 1, 20]

Solution

1. Step 1: Understand binary search LIS approach

   This method builds a list 'tails' where each element is the smallest possible tail of an increasing subsequence of given length.

2. Step 2: Trace the tails list for nums

   Start with empty tails:
   - 3: tails = [3]
   - 10: tails = [3, 10]
   - 2: replace 3 with 2, tails = [2, 10]
   - 1: replace 2 with 1, tails = [1, 10]
   - 20: tails = [1, 10, 20]
   The LIS length is 3, and one valid LIS is [3, 10, 20].

3. Final Answer:

   [3, 10, 20] -> Option A

4. Quick Check:

   Binary search LIS = [3, 10, 20] [OK]

Hint: Binary search builds tails array for LIS length [OK]

Common Mistakes:

• Confusing tails with actual subsequence
• Replacing wrong elements in tails
• Choosing subsequence with wrong order