Longest Increasing Subsequence in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of LIS length calculation

What is the output of the following C# code that calculates the length of the Longest Increasing Subsequence (LIS) for the given array?

DSA C#

using System;

class Program {
    static int LengthOfLIS(int[] nums) {
        int n = nums.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 (nums[i] > nums[j]) {
                    dp[i] = Math.Max(dp[i], dp[j] + 1);
                }
            }
        }
        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] > maxLen) maxLen = dp[i];
        }
        return maxLen;
    }

    static void Main() {
        int[] arr = {10, 9, 2, 5, 3, 7, 101, 18};
        Console.WriteLine(LengthOfLIS(arr));
    }
}

A 4

B 5

C 3

D 6

💡 Hint

Trace the dp array updates for each element comparing with previous elements.

The longest increasing subsequence is [2, 3, 7, 101] which has length 4, but the code also counts [2, 3, 7, 18] as length 4. The maximum length found is 4, but the code returns 4. The correct output is 4.

❓ Predict Output

intermediate

Output of LIS sequence reconstruction

What is the output of the following C# code that reconstructs one Longest Increasing Subsequence (LIS) from the given array?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static List<int> GetLIS(int[] nums) {
        int n = nums.Length;
        int[] dp = new int[n];
        int[] prev = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            prev[i] = -1;
        }
        int maxLen = 1, maxIndex = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    prev[i] = j;
                }
            }
            if (dp[i] >= maxLen) {
                maxLen = dp[i];
                maxIndex = i;
            }
        }
        List<int> lis = new List<int>();
        for (int i = maxIndex; i >= 0; i = prev[i]) {
            lis.Add(nums[i]);
            if (prev[i] == -1) break;
        }
        lis.Reverse();
        return lis;
    }

    static void Main() {
        int[] arr = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9};
        var lis = GetLIS(arr);
        Console.WriteLine(string.Join(", ", lis));
    }
}

A 0, 2, 6, 9

B 0, 8, 10, 14

C 0, 4, 6, 14

D 0, 4, 6, 9

💡 Hint

Follow the prev array to reconstruct the LIS from the maxIndex backwards.

The LIS found is [0, 4, 6, 9] which is one valid longest increasing subsequence for the input array.

🔧 Debug

advanced

Identify the error in LIS length calculation

What error does the following C# code produce when trying to calculate the length of the Longest Increasing Subsequence (LIS)?

DSA C#

using System;

class Program {
    static int LengthOfLIS(int[] nums) {
        int n = nums.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 (nums[i] > nums[j]) {
                    dp[i] = Math.Max(dp[i], dp[j] + 1);
                }
            }
        }
        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] > maxLen) maxLen = dp[i];
        }
        return maxLen;
    }

    static void Main() {
        int[] arr = {3, 10, 2, 1, 20};
        Console.WriteLine(LengthOfLIS(arr));
    }
}

A No error, outputs 3

B NullReferenceException

C IndexOutOfRangeException

D Compilation error due to missing semicolon

💡 Hint

Check the loop boundary conditions for i in the nested loops.

The outer loop uses 'i <= n' which causes i to go out of bounds when accessing nums[i] and dp[i], causing IndexOutOfRangeException.

🧠 Conceptual

advanced

Time complexity of LIS dynamic programming approach

What is the time complexity of the classic dynamic programming solution to find the length of the Longest Increasing Subsequence (LIS) using a dp array and nested loops?

A O(n^2)

B O(n log n)

C O(log n)

D O(n)

💡 Hint

Consider the nested loops iterating over the array elements.

The classic DP solution uses two nested loops each iterating up to n, resulting in O(n^2) time complexity.

🚀 Application

expert

Output of LIS length using binary search optimization

What is the output of the following C# code that calculates the length of the Longest Increasing Subsequence (LIS) using a binary search optimized approach?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static int LengthOfLIS(int[] nums) {
        List<int> sub = new List<int>();
        foreach (int x in nums) {
            int left = 0, right = sub.Count;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (sub[mid] < x) left = mid + 1;
                else right = mid;
            }
            if (right == sub.Count) sub.Add(x);
            else sub[right] = x;
        }
        return sub.Count;
    }

    static void Main() {
        int[] arr = {3, 5, 7, 1, 2, 8};
        Console.WriteLine(LengthOfLIS(arr));
    }
}

A 3

B 4

C 5

D 6

💡 Hint

The binary search approach builds a list representing the smallest possible tail for increasing subsequences of different lengths.

The LIS length is 4 for the subsequence [3, 5, 7, 8] or [1, 2, 7, 8]. The code returns 4.

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