Longest Increasing Subsequence in DSA Python

Mental Model

Find the longest sequence of numbers that keeps going up without skipping order. We want the biggest chain where each number is bigger than the one before.

Analogy: Imagine climbing stairs where each step is higher than the last. You want to find the longest path going up without stepping down or sideways.

Array: [10] -> [22] -> [9] -> [33] -> [21] -> [50] -> [41] -> [60]
LIS lengths: 1     2     1     3     2     4     4     5
↑ indices show current position

Dry Run Walkthrough

Input: array: [10, 22, 9, 33, 21, 50, 41, 60]

Goal: Find the length of the longest increasing subsequence in the array

Step 1: Start with first element 10, LIS length is 1

LIS lengths: [1, _, _, _, _, _, _, _]

Why: Each element alone is a subsequence of length 1

Step 2: Check 22: it is greater than 10, so LIS length at 22 is 1 + LIS at 10 = 2

LIS lengths: [1, 2, _, _, _, _, _, _]

Why: 22 can extend the subsequence ending at 10

Step 3: Check 9: smaller than 10 and 22, so LIS length is 1

LIS lengths: [1, 2, 1, _, _, _, _, _]

Why: 9 cannot extend any previous increasing subsequence

Step 4: Check 33: greater than 10, 22, and 9; max LIS length before is 2 (at 22), so LIS at 33 is 3

LIS lengths: [1, 2, 1, 3, _, _, _, _]

Why: 33 extends the longest subsequence ending at 22

Step 5: Check 21: greater than 10 and 9, but less than 22 and 33; max LIS before is 2 (at 10 or 9), so LIS at 21 is 3

LIS lengths: [1, 2, 1, 3, 3, _, _, _]

Why: 21 extends subsequence ending at 10 or 9

Step 6: Check 50: greater than all previous; max LIS before is 3 (at 33 or 21), so LIS at 50 is 4

LIS lengths: [1, 2, 1, 3, 3, 4, _, _]

Why: 50 extends the longest subsequence ending at 33 or 21

Step 7: Check 41: greater than 10, 22, 9, 33, 21; max LIS before is 3 (at 33 or 21), so LIS at 41 is 4

LIS lengths: [1, 2, 1, 3, 3, 4, 4, _]

Why: 41 extends the subsequence ending at 33 or 21

Step 8: Check 60: greater than all previous; max LIS before is 4 (at 50 or 41), so LIS at 60 is 5

LIS lengths: [1, 2, 1, 3, 3, 4, 4, 5]

Why: 60 extends the longest subsequence ending at 50 or 41

Result:

Longest Increasing Subsequence length is 5

Annotated Code

DSA Python

class LIS:
    def longest_increasing_subsequence(self, nums):
        n = len(nums)
        if n == 0:
            return 0
        lis = [1] * n  # Each element is at least length 1
        for i in range(1, n):
            for j in range(i):
                if nums[i] > nums[j]:
                    if lis[i] < lis[j] + 1:
                        lis[i] = lis[j] + 1  # Update LIS length at i
        return max(lis)

if __name__ == '__main__':
    arr = [10, 22, 9, 33, 21, 50, 41, 60]
    solver = LIS()
    result = solver.longest_increasing_subsequence(arr)
    print(result)

lis = [1] * n # Each element is at least length 1

Initialize LIS lengths to 1 for all elements

for i in range(1, n):

Traverse array from second element to end

for j in range(i):

Check all elements before i to find smaller values

if nums[i] > nums[j]:

Only consider increasing pairs

if lis[i] < lis[j] + 1:

Update LIS length at i if extending subsequence at j is longer

lis[i] = lis[j] + 1 # Update LIS length at i

Set new LIS length at i

return max(lis)

Return the maximum LIS length found

Output

5

Complexity Analysis

Time: O(n^2) because for each element we check all previous elements to update LIS length

Space: O(n) because we store LIS lengths for each element in an array

vs Alternative: This is better than checking all subsequences (which is exponential), but slower than advanced O(n log n) methods that use binary search

Edge Cases

empty array

returns 0 because no subsequence exists

DSA Python

if n == 0:
    return 0

array with all equal elements

returns 1 because longest increasing subsequence is any single element

DSA Python

lis = [1] * n  # Each element is at least length 1

strictly decreasing array

returns 1 because no element is greater than previous

DSA Python

if nums[i] > nums[j]:

When to Use This Pattern

When you need to find the longest ordered sequence inside an array where order matters but elements are not necessarily contiguous, use the Longest Increasing Subsequence pattern.

Common Mistakes

Mistake: Updating LIS length without checking if it improves the current value
Fix: Add condition to update only if new length is greater: if lis[i] < lis[j] + 1

Mistake: Comparing elements incorrectly (e.g., using >= instead of >)
Fix: Use strict greater than to ensure strictly increasing subsequence

Summary

Finds the length of the longest strictly increasing subsequence in an array.

Use when you want the longest chain of increasing numbers in order but not necessarily contiguous.

The key is to build up lengths by checking all smaller previous elements and extending their subsequences.

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