Longest Increasing Subsequence in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the length array for LIS calculation.

DSA C#

int[] lengths = new int[nums.Length];
for (int i = 0; i < nums.Length; i++) {
    lengths[i] = [1];
}

Drag options to blanks, or click blank then click option'

A1

Bnums[i]

C-1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing lengths with 0 instead of 1.

Using the element value instead of 1.

Each element starts with a length of 1 because the smallest increasing subsequence including that element is the element itself.

2fill in blank

medium

Complete the code to check if the current element can extend the subsequence ending at j.

DSA C#

for (int i = 1; i < nums.Length; i++) {
    for (int j = 0; j < i; j++) {
        if (nums[i] [1] nums[j]) {
            lengths[i] = Math.Max(lengths[i], lengths[j] + 1);
        }
    }
}

Drag options to blanks, or click blank then click option'

A>=

B<

C>

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using <= or >= which allows non-increasing sequences.

Using < which checks for decreasing sequences.

We want to find increasing subsequences, so nums[i] must be greater than nums[j] to extend the subsequence.

3fill in blank

hard

Fix the error in the code to find the maximum length of LIS after filling lengths array.

DSA C#

int maxLength = 0;
for (int i = 0; i < lengths.Length; i++) {
    if (lengths[i] [1] maxLength) {
        maxLength = lengths[i];
    }
}

Drag options to blanks, or click blank then click option'

A>

B<

C==

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' which finds minimum instead of maximum.

Using '==' which only updates if equal.

We update maxLength only if lengths[i] is greater than the current maxLength to find the maximum value.

4fill in blank

hard

Fill both blanks to complete the code that returns the length of the longest increasing subsequence.

DSA C#

public int LengthOfLIS(int[] nums) {
    int[] lengths = new int[nums.Length];
    for (int i = 0; i < nums.Length; i++) {
        lengths[i] = 1;
    }
    for (int i = 1; i < nums.Length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] [1] nums[j]) {
                lengths[i] = Math.Max(lengths[i], lengths[j] + 1);
            }
        }
    }
    return lengths.[2]();
}

Drag options to blanks, or click blank then click option'

A>

BSum

CMax

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using Sum() instead of Max() to find the longest subsequence.

Using '<' instead of '>' in the condition.

We check if nums[i] is greater than nums[j] to extend the subsequence, and return the maximum value in lengths array.

5fill in blank

hard

Fill all three blanks to complete the code that reconstructs the longest increasing subsequence.

DSA C#

public List<int> GetLIS(int[] nums) {
    int n = nums.Length;
    int[] lengths = new int[n];
    int[] previous = new int[n];
    for (int i = 0; i < n; i++) {
        lengths[i] = 1;
        previous[i] = -1;
    }
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] [1] nums[j] && lengths[j] + 1 > lengths[i]) {
                lengths[i] = lengths[j] + 1;
                previous[i] = j;
            }
        }
    }
    int maxIndex = 0;
    for (int i = 1; i < n; i++) {
        if (lengths[i] [2] lengths[maxIndex]) {
            maxIndex = i;
        }
    }
    List<int> lis = new List<int>();
    for (int i = maxIndex; i != [3]; i = previous[i]) {
        lis.Add(nums[i]);
    }
    lis.Reverse();
    return lis;
}

Drag options to blanks, or click blank then click option'

A>

B<

C0

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' in comparisons.

Using 0 instead of -1 as the stopping condition.

We check if nums[i] > nums[j] to extend subsequence, update maxIndex if lengths[i] > lengths[maxIndex], and stop reconstruction when previous index is -1.

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