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

↓

Return max LIS length

We start with the array and build an LIS array where each position stores the length of the longest increasing subsequence ending there. We update LIS values by checking previous elements smaller than current. Finally, we find the maximum LIS length.

Execution Sample

DSA C

int lengthOfLIS(int* nums, int numsSize) {
  int LIS[numsSize];
  for (int i = 0; i < numsSize; i++) LIS[i] = 1;
  for (int i = 1; i < numsSize; i++) {
    for (int j = 0; j < i; j++) {
      if (nums[j] < nums[i] && LIS[j] + 1 > LIS[i]) LIS[i] = LIS[j] + 1;
    }
  }
  int max = 1;
  for (int i = 0; i < numsSize; i++) if (LIS[i] > max) max = LIS[i];
  return max;
}

This code calculates the length of the longest increasing subsequence in the given array.

Execution Table

Step	Operation	i	j	Condition (nums[j]<nums[i])	Condition (LIS[j]+1 > LIS[i])	LIS Array State	Max LIS So Far
Init	Initialize LIS array	-	-	-	-	[1, 1, 1, 1, 1]	1
1	Check j=0 for i=1	1	0	5 < 7: True	1+1 > 1: True	[1, 2, 1, 1, 1]	2
2	Check j=0 for i=2	2	0	5 < 4: False	-	[1, 2, 1, 1, 1]	2
3	Check j=1 for i=2	2	1	7 < 4: False	-	[1, 2, 1, 1, 1]	2
4	Check j=0 for i=3	3	0	5 < 8: True	1+1 > 1: True	[1, 2, 1, 2, 1]	2
5	Check j=1 for i=3	3	1	7 < 8: True	2+1 > 2: True	[1, 2, 1, 3, 1]	3
6	Check j=2 for i=3	3	2	4 < 8: True	1+1 > 3: False	[1, 2, 1, 3, 1]	3
7	Check j=0 for i=4	4	0	5 < 9: True	1+1 > 1: True	[1, 2, 1, 3, 2]	3
8	Check j=1 for i=4	4	1	7 < 9: True	2+1 > 2: True	[1, 2, 1, 3, 3]	3
9	Check j=2 for i=4	4	2	4 < 9: True	1+1 > 3: False	[1, 2, 1, 3, 3]	3
10	Check j=3 for i=4	4	3	8 < 9: True	3+1 > 3: True	[1, 2, 1, 3, 4]	4
End	Find max LIS	-	-	-	-	[1, 2, 1, 3, 4]	4

💡 All elements processed; maximum LIS length found as 4.

Variable Tracker

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

Key Moments - 3 Insights

Why do we initialize all LIS values to 1 at the start?

Because each element alone is an increasing subsequence of length 1. This is shown in the 'Init' row of the execution_table where LIS starts as [1,1,1,1,1].

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. This prevents overwriting with shorter subsequences, as seen in steps 6 and 9 where updates are skipped.

How do we find the final longest increasing subsequence length?

After filling the LIS array, we scan it to find the maximum value, which represents the longest subsequence length. This is shown in the 'End' step where max LIS is 4.

Visual Quiz - 3 Questions

Look at the execution_table at Step 5. What is the LIS array state?

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

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

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

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

💡 Hint

Check the LIS Array State column at Step 5 in the execution_table.

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

A Step 4

B Step 6

C Step 5

D Step 8

💡 Hint

Look at the Max LIS So Far column in the execution_table rows.

If the input array was strictly decreasing, how would the LIS array look after initialization and processing?

A All values remain 1

B Values increase progressively

C Values become zero

D Values alternate between 1 and 2

💡 Hint

Refer to the variable_tracker and key_moments about LIS initialization and updates.

Concept Snapshot

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

Full Transcript

Longest Increasing Subsequence finds the longest sequence of increasing numbers in an array. We start by setting each element's LIS value 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 can extend a longer subsequence, we update the current element's LIS value. 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 longest subsequence where each number is larger than the previous one

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

C. The longest subsequence where numbers are equal

D. The shortest subsequence with increasing numbers

Solution

1. Step 1: Understand the LIS definition

   The Longest Increasing Subsequence is a subsequence where every next number is strictly greater than the previous one.

2. Step 2: Compare options with the definition

   The longest subsequence where each number is larger than the previous one matches the definition exactly. Options B, C, and D do not describe LIS correctly.

3. Final Answer:

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

4. Quick Check:

   LIS = longest increasing subsequence [OK]

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

Common Mistakes:

• Confusing increasing with non-decreasing
• Thinking LIS means equal numbers
• Mixing up subsequence with substring

2. Which of the following C code snippets correctly initializes the array to store LIS lengths for each element in an array arr of size n?

easy

A. int lis[n] = {0};

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

C. int lis[n]; for(int i=0; i

D. int lis[n]; memset(lis, 1, n*sizeof(int));

Solution

1. Step 1: Understand LIS initialization

   Each element starts with LIS length 1 because each element alone is a subsequence.

2. Step 2: Check code correctness

   int lis[n]; for(int i=0; i

3. Final Answer:

   int lis[n]; for(int i=0; i -> Option B

4. Quick Check:

   Initialize LIS array with 1 [OK]

Hint: Initialize LIS array elements to 1, not 0 [OK]

Common Mistakes:

• Using memset to set integers to 1 (wrong)
• Initializing LIS array with zeros
• Not initializing LIS array at all

3. What is the output of the following C code snippet that calculates the length of LIS for array arr = {10, 22, 9, 33, 21, 50, 41, 60}?

int arr[] = {10, 22, 9, 33, 21, 50, 41, 60};
int n = 8;
int lis[8];
for(int i=0; i arr[j] && lis[i] < lis[j] + 1) {
      lis[i] = lis[j] + 1;
    }
  }
}
int max = lis[0];
for(int i=1; i max) max = lis[i];
}
printf("%d", max);

medium

A. 4

B. 6

C. 5

D. 3

Solution

1. Step 1: Calculate LIS values step-by-step

   Start with lis = {1,1,1,1,1,1,1,1} - i=1: arr[1]=22 > arr[0]=10, lis[1]=max(1,1+1)=2 - i=2: arr[2]=9 no smaller than previous, lis[2]=1 - i=3: arr[3]=33 > 22 and 10, lis[3]=max(1,2+1)=3 - i=4: arr[4]=21 > 10 but <22, lis[4]=max(1,1+1)=2 - i=5: arr[5]=50 > 33, 22, 21, lis[5]=max(1,3+1)=4 - i=6: arr[6]=41 > 33, 22, 21, lis[6]=max(1,3+1)=4 - i=7: arr[7]=60 > 50, 41, lis[7]=max(1,4+1)=5

2. Step 2: Find maximum LIS length

   Maximum value in lis array is 5.

3. Final Answer:

   5 -> Option C

4. Quick Check:

   LIS length for given array = 5 [OK]

Hint: Trace LIS array updates carefully for each element [OK]

Common Mistakes:

• Counting non-increasing subsequences
• Forgetting to update lis[i] only if condition met
• Mixing up indices in nested loops

4. Identify the bug in the following C code snippet that attempts to compute the LIS length:

int arr[] = {3, 10, 2, 1, 20};
int n = 5;
int lis[5];
for(int i=0; i arr[j] && lis[i] < lis[j] + 1) {
      lis[i] = lis[j] + 1;
    }
  }
}
int max = lis[0];
for(int i=1; i max) max = lis[i];
}
printf("%d", max);

medium

A. LIS array should be initialized with 1, not 0

B. The nested loops should start from i=0

C. The condition arr[i] > arr[j] should be arr[i] >= arr[j]

D. The max variable should be initialized to 0

Solution

1. Step 1: Check LIS array initialization

   LIS array elements represent length of subsequence ending at each index. Each element alone forms subsequence of length 1, so initialize lis[i] = 1.

2. Step 2: Analyze effect of initialization

   Initializing lis[i] = 0 causes all comparisons lis[i] < lis[j] + 1 to fail or produce wrong results, leading to incorrect max LIS length.

3. Final Answer:

   LIS array should be initialized with 1, not 0 -> Option A

4. Quick Check:

   Initialize LIS array with 1 to avoid zero-length subsequences [OK]

Hint: Always start LIS lengths at 1, not 0 [OK]

Common Mistakes:

• Initializing LIS array with zeros
• Changing comparison operators incorrectly
• Starting loops at wrong indices

5. Given an array arr = {5, 7, 4, 8, 6, 9}, write a C function to find the length of the Longest Increasing Subsequence using dynamic programming. What is the length of the LIS for this array?

hard

A. 6

B. 3

C. 5

D. 4

Solution

1. Step 1: Initialize LIS array with 1 for each element

   lis = {1,1,1,1,1,1}

2. Step 2: Update LIS values by comparing each element with previous ones

   - i=1 (7): 7 > 5, lis[1] = max(1, 1+1) = 2 - i=2 (4): 4 > 5? No, lis[2] = 1 - i=3 (8): 8 > 5, lis[3] = max(1,1+1)=2; 8 > 7, lis[3] = max(2,2+1)=3; 8 > 4, lis[3] = max(3,1+1)=3 - i=4 (6): 6 > 5, lis[4] = max(1,1+1)=2; 6 > 7? No; 6 > 4, lis[4] = max(2,1+1)=2; 6 > 8? No - i=5 (9): 9 > 5, lis[5] = max(1,1+1)=2; 9 > 7, lis[5] = max(2,2+1)=3; 9 > 4, lis[5] = max(3,1+1)=3; 9 > 8, lis[5] = max(3,3+1)=4; 9 > 6, lis[5] = max(4,2+1)=4

3. Step 3: Find maximum LIS length

   Maximum lis value is 4.

4. Final Answer:

   4 -> Option D

5. Quick Check:

   LIS length for given array = 4 [OK]

Hint: Update LIS by checking all previous smaller elements [OK]

Common Mistakes:

• Not updating LIS correctly for all previous elements
• Confusing subsequence with substring
• Forgetting to initialize LIS array with 1