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.