Longest Increasing Subsequence in DSA Python - Execution Trace

Concept Flow - Longest Increasing Subsequence

Start with array

↓

Initialize LIS array with 1s

↓

For each element i from 1 to end

↓

For each element j before i

↓

Check if arr[j

Yes↓

Update LIS[i

↓

Repeat for all i

↓

Find max value in LIS array

↓

Return max LIS length

We start with the array and create a LIS array to store lengths. For each element, we check all previous elements to update LIS values. Finally, we find the longest length.

Execution Sample

DSA Python

arr = [10, 22, 9, 33, 21, 50, 41, 60]
LIS = [1]*len(arr)
for i in range(1, len(arr)):
    for j in range(i):
        if arr[j] < arr[i] and LIS[i] < LIS[j] + 1:
            LIS[i] = LIS[j] + 1
print(max(LIS))

This code finds the length of the longest increasing subsequence in the array.

Execution Table

Step	Operation	i	j	Condition arr[j]<arr[i]	Condition LIS[i]<LIS[j]+1	LIS Array State	Max LIS So Far
1	Initialize LIS	-	-	-	-	[1, 1, 1, 1, 1, 1, 1, 1]	1
2	i=1, j=0 check	1	0	10 < 22: True	1 < 1+1: True	[1, 2, 1, 1, 1, 1, 1, 1]	2
3	i=2, j=0 check	2	0	10 < 9: False	-	[1, 2, 1, 1, 1, 1, 1, 1]	2
4	i=2, j=1 check	2	1	22 < 9: False	-	[1, 2, 1, 1, 1, 1, 1, 1]	2
5	i=3, j=0 check	3	0	10 < 33: True	1 < 1+1: True	[1, 2, 1, 2, 1, 1, 1, 1]	2
6	i=3, j=1 check	3	1	22 < 33: True	2 < 2+1: True	[1, 2, 1, 3, 1, 1, 1, 1]	3
7	i=3, j=2 check	3	2	9 < 33: True	3 < 1+1: False	[1, 2, 1, 3, 1, 1, 1, 1]	3
8	i=4, j=0 check	4	0	10 < 21: True	1 < 1+1: True	[1, 2, 1, 3, 2, 1, 1, 1]	3
9	i=4, j=1 check	4	1	22 < 21: False	-	[1, 2, 1, 3, 2, 1, 1, 1]	3
10	i=4, j=2 check	4	2	9 < 21: True	2 < 1+1: False	[1, 2, 1, 3, 2, 1, 1, 1]	3
11	i=4, j=3 check	4	3	33 < 21: False	-	[1, 2, 1, 3, 2, 1, 1, 1]	3
12	i=5, j=0 check	5	0	10 < 50: True	1 < 1+1: True	[1, 2, 1, 3, 2, 2, 1, 1]	3
13	i=5, j=1 check	5	1	22 < 50: True	2 < 2+1: True	[1, 2, 1, 3, 2, 3, 1, 1]	3
14	i=5, j=2 check	5	2	9 < 50: True	3 < 1+1: False	[1, 2, 1, 3, 2, 3, 1, 1]	3
15	i=5, j=3 check	5	3	33 < 50: True	3 < 3+1: True	[1, 2, 1, 3, 2, 4, 1, 1]	4
16	i=5, j=4 check	5	4	21 < 50: True	4 < 2+1: False	[1, 2, 1, 3, 2, 4, 1, 1]	4
17	i=6, j=0 check	6	0	10 < 41: True	1 < 1+1: True	[1, 2, 1, 3, 2, 4, 2, 1]	4
18	i=6, j=1 check	6	1	22 < 41: True	2 < 2+1: True	[1, 2, 1, 3, 2, 4, 3, 1]	4
19	i=6, j=2 check	6	2	9 < 41: True	3 < 1+1: False	[1, 2, 1, 3, 2, 4, 3, 1]	4
20	i=6, j=3 check	6	3	33 < 41: True	3 < 3+1: True	[1, 2, 1, 3, 2, 4, 4, 1]	4
21	i=6, j=4 check	6	4	21 < 41: True	4 < 2+1: False	[1, 2, 1, 3, 2, 4, 4, 1]	4
22	i=6, j=5 check	6	5	50 < 41: False	-	[1, 2, 1, 3, 2, 4, 4, 1]	4
23	i=7, j=0 check	7	0	10 < 60: True	1 < 1+1: True	[1, 2, 1, 3, 2, 4, 4, 2]	4
24	i=7, j=1 check	7	1	22 < 60: True	2 < 2+1: True	[1, 2, 1, 3, 2, 4, 4, 3]	4
25	i=7, j=2 check	7	2	9 < 60: True	3 < 1+1: False	[1, 2, 1, 3, 2, 4, 4, 3]	4
26	i=7, j=3 check	7	3	33 < 60: True	3 < 3+1: True	[1, 2, 1, 3, 2, 4, 4, 4]	4
27	i=7, j=4 check	7	4	21 < 60: True	4 < 2+1: False	[1, 2, 1, 3, 2, 4, 4, 4]	4
28	i=7, j=5 check	7	5	50 < 60: True	4 < 4+1: True	[1, 2, 1, 3, 2, 4, 4, 5]	5
29	i=7, j=6 check	7	6	41 < 60: True	5 < 4+1: False	[1, 2, 1, 3, 2, 4, 4, 5]	5
30	End	-	-	-	-	[1, 2, 1, 3, 2, 4, 4, 5]	5

💡 All elements processed, maximum LIS length found as 5

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	Final
i	-	1	2	3	4	5	6	7	-
j	-	0	1	2	3	4	5	6	-
LIS	[1,1,1,1,1,1,1,1]	[1,2,1,1,1,1,1,1]	[1,2,1,1,1,1,1,1]	[1,2,1,3,1,1,1,1]	[1,2,1,3,2,1,1,1]	[1,2,1,3,2,4,1,1]	[1,2,1,3,2,4,4,1]	[1,2,1,3,2,4,4,5]	[1,2,1,3,2,4,4,5]
Max LIS	1	2	2	3	3	4	4	5	5

Key Moments - 3 Insights

Why do we initialize the LIS array with all 1s at the start?

Because each element alone is an increasing subsequence of length 1. This is shown in execution_table row 1 where LIS starts as all ones.

Why do we check both conditions arr[j] < arr[i] and LIS[i] < LIS[j] + 1 before updating LIS[i]?

We only update LIS[i] if arr[j] is smaller (to keep increasing order) and if extending the subsequence ending at j makes LIS[i] longer. This is clear in rows like 2 and 6 where both conditions are true.

Why does the maximum LIS length appear at the end and not necessarily at the last element?

Because the longest subsequence can end anywhere in the array. We track max LIS so far in each step (see Max LIS column), and final max is the answer.

Visual Quiz - 3 Questions

Look at the execution_table at step 6. What is the LIS array state after updating?

A [1, 2, 1, 3, 1, 1, 1, 1]

B [1, 2, 1, 2, 1, 1, 1, 1]

C [1, 1, 1, 3, 1, 1, 1, 1]

D [1, 2, 2, 3, 1, 1, 1, 1]

💡 Hint

Check execution_table row 6 under 'LIS Array State' column.

At which step does the maximum LIS length first become 4?

A Step 15

B Step 13

C Step 20

D Step 28

💡 Hint

Look at the 'Max LIS So Far' column in execution_table rows around 13-20.

If the array started with [10, 5, 22], how would the LIS array change after i=1?

A [1, 2, 1]

B [1, 1, 1]

C [1, 1, 2]

D [2, 1, 1]

💡 Hint

Since 10 < 5 is false, LIS[1] remains 1 as per the condition in execution_table rows 3 and 4.

Concept Snapshot

Longest Increasing Subsequence (LIS):
- Initialize LIS array with 1s (each element alone)
- For each element i, check all previous j < i
- If arr[j] < arr[i] and LIS[i] < LIS[j] + 1, update LIS[i]
- Result is max value in LIS array
- Time complexity O(n^2), space O(n)

Full Transcript

Longest Increasing Subsequence finds the longest sequence of increasing numbers in an array. We create an array LIS where each position starts at 1, meaning each element alone is a subsequence. For each element, we look back at all previous elements. If a previous element is smaller and extending its subsequence makes a longer subsequence, we update the current LIS value. After processing all elements, the maximum value in LIS is the length of the longest increasing subsequence. This process is shown step-by-step in the execution table, tracking how LIS changes and the maximum length found so far.

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