Longest Increasing Subsequence in DSA C# - Build from Scratch

Longest Increasing Subsequence

📖 Scenario: You are working on a fitness app that tracks daily step counts. You want to find the longest streak of days where the step count increased compared to the previous day. This helps users see their longest period of improvement.

🎯 Goal: Build a program that finds the length of the longest increasing subsequence of daily step counts.

📋 What You'll Learn

Create an integer array called steps with the exact values: 1000, 1200, 1100, 1300, 1400, 1250, 1500

Create an integer array called lis to store the length of the longest increasing subsequence ending at each index

Use a nested for loop with variables i and j to compute the lis values

Find the maximum value in lis and print it as the longest increasing subsequence length

💡 Why This Matters

🌍 Real World

Tracking progress in fitness or learning apps by finding longest streaks of improvement.

💼 Career

Understanding dynamic programming and array manipulation is key for software development and algorithm design roles.

1

Create the steps data array

Create an integer array called steps with these exact values: 1000, 1200, 1100, 1300, 1400, 1250, 1500

DSA C#

// Create the steps array with the given values
// Your code here

Hint

Use int[] steps = { ... }; to create the array with the exact numbers.

2

Initialize the LIS array

Create an integer array called lis with the same length as steps. Initialize all elements of lis to 1 because the smallest increasing subsequence at each position is the element itself.

DSA C#

int[] steps = {1000, 1200, 1100, 1300, 1400, 1250, 1500};
// Create the lis array and initialize all elements to 1
// Your code here

Hint

Use a for loop to set each element of lis to 1.

3

Compute the LIS values

Use a nested for loop with variables i and j where i goes from 1 to steps.Length - 1 and j goes from 0 to i - 1. Inside the inner loop, if steps[i] is greater than steps[j] and lis[i] is less than lis[j] + 1, update lis[i] to lis[j] + 1.

DSA C#

int[] steps = {1000, 1200, 1100, 1300, 1400, 1250, 1500};
int[] lis = new int[steps.Length];
for (int i = 0; i < lis.Length; i++)
{
    lis[i] = 1;
}
// Use nested for loops to update lis values
// Your code here

Hint

Use two loops: outer loop from 1 to end, inner loop from 0 to i-1. Update lis[i] when conditions meet.

4

Print the longest increasing subsequence length

Find the maximum value in the lis array and print it using Console.WriteLine with the exact text: Longest increasing subsequence length: X where X is the maximum value.

DSA C#

int[] steps = {1000, 1200, 1100, 1300, 1400, 1250, 1500};
int[] lis = new int[steps.Length];
for (int i = 0; i  steps[j] && lis[i] < lis[j] + 1)
        {
            lis[i] = lis[j] + 1;
        }
    }
}
// Find max in lis and print the result
// Your code here

Hint

Use a loop to find the maximum value in lis. Then print it with the exact text.

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