Longest Increasing Subsequence in DSA C# - Execution Trace

Concept Flow - Longest Increasing Subsequence

Start with array

↓

Initialize LIS array with 1s

↓

For each element i

↓

Check all elements j < i

↓

If arr[j

↓

Update LIS[i

↓

Repeat for all i

↓

Find max value in LIS array

↓

Result: length of longest increasing subsequence

We start with the array, build an LIS array storing longest subsequence lengths ending at each index, update it by checking previous elements, and finally find the maximum LIS value.

Execution Sample

DSA C#

int[] arr = {10, 9, 2, 5, 3, 7, 101, 18};
int[] lis = new int[arr.Length];
for (int i = 0; i < arr.Length; i++) lis[i] = 1;
for (int i = 1; i < arr.Length; i++) {
  for (int j = 0; j < i; j++) {
    if (arr[j] < arr[i] && lis[j] + 1 > lis[i]) lis[i] = lis[j] + 1;
  }
}
int maxLIS = lis.Max();

This code finds the length of the longest increasing subsequence in the array by building the lis array step-by-step.

Execution Table

Step	Operation	Index i	Index j	Condition arr[j]<arr[i]	Condition lis[j]+1>lis[i]	LIS Array State	Visual State
1	Initialize LIS	-	-	-	-	[1, 1, 1, 1, 1, 1, 1, 1]	Each element starts with LIS=1
2	i=1, j=0	1	0	arr[0]=10 < arr[1]=9? No	-	[1, 1, 1, 1, 1, 1, 1, 1]	No update since 10<9 is false
3	i=2, j=0	2	0	10 < 2? No	-	[1, 1, 1, 1, 1, 1, 1, 1]	No update
4	i=2, j=1	2	1	9 < 2? No	-	[1, 1, 1, 1, 1, 1, 1, 1]	No update
5	i=3, j=0	3	0	10 < 5? No	-	[1, 1, 1, 1, 1, 1, 1, 1]	No update
6	i=3, j=1	3	1	9 < 5? No	-	[1, 1, 1, 1, 1, 1, 1, 1]	No update
7	i=3, j=2	3	2	2 < 5? Yes	1+1 > 1? Yes	[1, 1, 1, 2, 1, 1, 1, 1]	LIS[3] updated to 2
8	i=4, j=0	4	0	10 < 3? No	-	[1, 1, 1, 2, 1, 1, 1, 1]	No update
9	i=4, j=1	4	1	9 < 3? No	-	[1, 1, 1, 2, 1, 1, 1, 1]	No update
10	i=4, j=2	4	2	2 < 3? Yes	1+1 > 1? Yes	[1, 1, 1, 2, 2, 1, 1, 1]	LIS[4] updated to 2
11	i=4, j=3	4	3	5 < 3? No	-	[1, 1, 1, 2, 2, 1, 1, 1]	No update
12	i=5, j=0	5	0	10 < 7? No	-	[1, 1, 1, 2, 2, 1, 1, 1]	No update
13	i=5, j=1	5	1	9 < 7? No	-	[1, 1, 1, 2, 2, 1, 1, 1]	No update
14	i=5, j=2	5	2	2 < 7? Yes	1+1 > 1? Yes	[1, 1, 1, 2, 2, 2, 1, 1]	LIS[5] updated to 2
15	i=5, j=3	5	3	5 < 7? Yes	2+1 > 2? Yes	[1, 1, 1, 2, 2, 3, 1, 1]	LIS[5] updated to 3
16	i=5, j=4	5	4	3 < 7? Yes	2+1 > 3? No	[1, 1, 1, 2, 2, 3, 1, 1]	No update
17	i=6, j=0	6	0	10 < 101? Yes	1+1 > 1? Yes	[1, 1, 1, 2, 2, 3, 2, 1]	LIS[6] updated to 2
18	i=6, j=1	6	1	9 < 101? Yes	1+1 > 2? No	[1, 1, 1, 2, 2, 3, 2, 1]	No update
19	i=6, j=2	6	2	2 < 101? Yes	1+1 > 2? No	[1, 1, 1, 2, 2, 3, 2, 1]	No update
20	i=6, j=3	6	3	5 < 101? Yes	2+1 > 2? Yes	[1, 1, 1, 2, 2, 3, 3, 1]	LIS[6] updated to 3
21	i=6, j=4	6	4	3 < 101? Yes	2+1 > 3? No	[1, 1, 1, 2, 2, 3, 3, 1]	No update
22	i=6, j=5	6	5	7 < 101? Yes	3+1 > 3? Yes	[1, 1, 1, 2, 2, 3, 4, 1]	LIS[6] updated to 4
23	i=7, j=0	7	0	10 < 18? Yes	1+1 > 1? Yes	[1, 1, 1, 2, 2, 3, 4, 2]	LIS[7] updated to 2
24	i=7, j=1	7	1	9 < 18? Yes	1+1 > 2? No	[1, 1, 1, 2, 2, 3, 4, 2]	No update
25	i=7, j=2	7	2	2 < 18? Yes	1+1 > 2? No	[1, 1, 1, 2, 2, 3, 4, 2]	No update
26	i=7, j=3	7	3	5 < 18? Yes	2+1 > 2? Yes	[1, 1, 1, 2, 2, 3, 4, 3]	LIS[7] updated to 3
27	i=7, j=4	7	4	3 < 18? Yes	2+1 > 3? No	[1, 1, 1, 2, 2, 3, 4, 3]	No update
28	i=7, j=5	7	5	7 < 18? Yes	3+1 > 3? Yes	[1, 1, 1, 2, 2, 3, 4, 4]	LIS[7] updated to 4
29	i=7, j=6	7	6	101 < 18? No	-	[1, 1, 1, 2, 2, 3, 4, 4]	No update
30	Find max LIS	-	-	-	-	[1, 1, 1, 2, 2, 3, 4, 4]	Max LIS is 4
31	End	-	-	-	-	[1, 1, 1, 2, 2, 3, 4, 4]	Algorithm finished

💡 All elements processed, LIS array fully updated, maximum LIS found

Variable Tracker

Variable	Start	After Step 1	After Step 7	After Step 11	After Step 16	After Step 22	After Step 29	Final
LIS	-	[1,1,1,1,1,1,1,1]	[1,1,1,2,1,1,1,1]	[1,1,1,2,2,1,1,1]	[1,1,1,2,2,3,1,1]	[1,1,1,2,2,3,4,1]	[1,1,1,2,2,3,4,4]	[1,1,1,2,2,3,4,4]
i	-	-	3	4	5	6	7	-
j	-	-	2	4	5	6	6	-

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 1s.

Why do we check if lis[j] + 1 > lis[i] before updating LIS[i]?

To ensure we only update LIS[i] if we found a longer increasing subsequence ending at i. See rows 7, 10, 15 where LIS[i] updates only when this condition is true.

Why does the algorithm compare arr[j] < arr[i]?

Because the subsequence must be strictly increasing. We only extend subsequences where the previous element is smaller. This condition is checked in every inner loop step, e.g., row 7.

Visual Quiz - 3 Questions

Look at the execution_table at step 15. What is the LIS array state after this step?

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

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

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

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

💡 Hint

Check the LIS Array State column at step 15 in execution_table

At which step does the LIS value at index 6 first become 4?

A Step 20

B Step 22

C Step 18

D Step 29

💡 Hint

Look at LIS updates for index 6 in execution_table rows 20-22

If the input array was strictly decreasing, what would the final LIS array look like?

A Increasing values from 1 to n

B All elements would be 0

C All elements would be 1

D Random values

💡 Hint

Refer to variable_tracker start and final LIS values for non-increasing sequences

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[j]+1 > LIS[i], update LIS[i]
- Result is max value in LIS array
- Time complexity: O(n^2) for this approach

Full Transcript

Longest Increasing Subsequence finds the longest strictly increasing sequence inside an array. We start by setting each element's LIS to 1 because each element alone is a subsequence. Then 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 element's LIS. After processing all elements, the maximum LIS value is the length of the longest increasing subsequence. This process is shown step-by-step in the execution table and variable tracker.

Practice

1. What does the Longest Increasing Subsequence (LIS) problem ask you to find in a sequence of numbers?

easy

A. The shortest subsequence with increasing numbers

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

C. The longest subsequence where numbers are equal

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

Solution

1. Step 1: Understand the problem definition

   The LIS problem looks for a subsequence where every next number is bigger than the one before it.

2. Step 2: Compare options with the definition

   Only The longest subsequence where each number is larger than the previous one matches this definition exactly.

3. Final Answer:

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

4. Quick Check:

   LIS = increasing subsequence [OK]

Hint: LIS means strictly increasing numbers in order [OK]

Common Mistakes:

• Confusing increasing with decreasing subsequence
• Thinking LIS means contiguous elements
• Assuming equal numbers count as increasing

2. Which of the following C# code snippets correctly initializes an array to find LIS length?

easy

A. int[] dp = new int[n]; for(int i=0; i

B. int dp[] = new int[n]; for(int i=0; i

C. int[] dp = new int[n]; for(int i=0; i<=n; i++) dp[i] = 1;

D. int[] dp = new int[n+1]; for(int i=1; i<=n; i++) dp[i] = 1;

Solution

1. Step 1: Check array initialization syntax

   int[] dp = new int[n]; for(int i=0; i

2. Step 2: Identify errors in other options

   int dp[] = new int[n]; for(int i=0; i

3. Final Answer:

   int[] dp = new int[n]; for(int i=0; i -> Option A

4. Quick Check:

   Correct array init and loop range [OK]

Hint: Use zero-based indexing and initialize dp with 1 [OK]

Common Mistakes:

• Using wrong loop bounds causing index errors
• Initializing dp elements to 0 instead of 1
• Incorrect array declaration syntax

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

int[] arr = {10, 22, 9, 33, 21, 50, 41, 60};
int n = arr.Length;
int[] dp = new int[n];
for (int i = 0; i < n; i++) dp[i] = 1;
for (int i = 1; i < n; i++) {
  for (int j = 0; j < i; j++) {
    if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
      dp[i] = dp[j] + 1;
    }
  }
}
int max = 0;
for (int i = 0; i < n; i++) {
  if (dp[i] > max) max = dp[i];
}
Console.WriteLine(max);

medium

A. 5

B. 4

C. 6

D. 3

Solution

1. Step 1: Trace dp array updates for LIS length

   Initial dp = [1,1,1,1,1,1,1,1]. Update dp as we find increasing subsequences: - i=1: arr[1]=22 > arr[0]=10, dp[1]=max(1, dp[0]+1)=2 - i=2: arr[2]=9 no update - i=3: arr[3]=33 > 22, dp[3]=max(1, dp[1]+1)=3 - i=4: arr[4]=21 > 10, dp[4]=2; also 21 < 22 no update - i=5: arr[5]=50 > 33, dp[5]=max(1, dp[3]+1)=4 - i=6: arr[6]=41 > 33, dp[6]=max(1, dp[3]+1)=4; also 41 > 21 dp[4]+1=3 no update - i=7: arr[7]=60 > 50 dp[5]+1=5, dp[7]=5 Final dp = [1,2,1,3,2,4,4,5]

2. Step 2: Find max value in dp

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

3. Final Answer:

   5 -> Option A

4. Quick Check:

   LIS length = 5 [OK]

Hint: Track dp updates for each element comparing previous smaller elements [OK]

Common Mistakes:

• Not updating dp[i] correctly inside nested loops
• Confusing max dp value with sum of elements
• Off-by-one errors in loops

4. Identify the bug in this LIS code snippet and choose the correct fix:

int[] arr = {3, 10, 2, 1, 20};
int n = arr.Length;
int[] dp = new int[n];
for (int i = 0; i <= n; i++) dp[i] = 1;  // Bug here
for (int i = 1; i < n; i++) {
  for (int j = 0; j < i; j++) {
    if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
      dp[i] = dp[j] + 1;
    }
  }
}
int max = dp[0];
for (int i = 1; i < n; i++) {
  if (dp[i] > max) max = dp[i];
}
Console.WriteLine(max);

medium

A. Remove the initialization loop entirely

B. Change 'i <= n' to 'i < n' in the initialization loop

C. Change inner loop to 'for (int j = 1; j < i; j++)'

D. Initialize dp array with zeros instead of ones

Solution

1. Step 1: Identify the cause of runtime error

   The loop 'for (int i = 0; i <= n; i++)' tries to access dp[n], which is out of bounds since dp size is n (0 to n-1).

2. Step 2: Fix the loop condition

   Changing the loop condition to 'i < n' prevents out-of-range access and correctly initializes all dp elements to 1.

3. Final Answer:

   Change 'i <= n' to 'i < n' in the initialization loop -> Option B

4. Quick Check:

   Loop bounds must match array size [OK]

Hint: Check loop bounds carefully to avoid index errors [OK]

Common Mistakes:

• Using <= instead of < in loops over arrays
• Initializing dp with zeros causing wrong LIS length
• Changing inner loop start incorrectly

5. Given the sequence {5, 7, 4, 8, 6, 9}, what is the length of the Longest Increasing Subsequence if you must also skip any number that is even?

hard

A. 4

B. 2

C. 3

D. 1

Solution

1. Step 1: Filter out even numbers from the sequence

   Original: 5, 7, 4, 8, 6, 9 Remove even: 5, 7, 9

2. Step 2: Find LIS length on filtered sequence

   Sequence is 5, 7, 9 which is strictly increasing. Length = 3. But question says "must also skip any number that is even" so 4,8,6 are removed. However, 7 is odd, so sequence is 5,7,9.

3. Step 3: Re-examine options and question carefully

   Wait, the question says "must also skip any number that is even" meaning we cannot include even numbers in LIS. So LIS is on 5,7,9 with length 3. But options do not have 3 as correct answer except 3. Check if 7 is odd? Yes. So LIS length is 3.

4. Final Answer:

   3 -> Option C

5. Quick Check:

   Filter evens, LIS length = 3 [OK]

Hint: Filter out evens first, then find LIS length [OK]

Common Mistakes:

• Including even numbers in LIS calculation
• Confusing subsequence with substring
• Miscounting length after filtering