Longest Increasing Subsequence in DSA C#

Mental Model

Find the longest sequence of numbers that keeps going up without skipping order.

Analogy: Imagine climbing stairs where each step is higher than the last. You want the longest path going up without stepping down.

Array: [10] -> [22] -> [9] -> [33] -> [21] -> [50] -> [41] -> [60]
LIS length at each index: [1] -> [2] -> [1] -> [3] -> [2] -> [4] -> [4] -> [5]

Dry Run Walkthrough

Input: array: [10, 22, 9, 33, 21, 50, 41, 60]

Goal: Find the length of the longest increasing subsequence in the array

Step 1: Start with first element 10, LIS length is 1

LIS lengths: [1] -> [] -> [] -> [] -> [] -> [] -> [] -> []

Why: Each element alone is a subsequence of length 1

Step 2: Check 22: it is greater than 10, so LIS length at 22 is 1 + LIS at 10 = 2

LIS lengths: [1] -> [2] -> [] -> [] -> [] -> [] -> [] -> []

Why: 22 can extend the subsequence ending at 10

Step 3: Check 9: smaller than 10 and 22, so LIS length is 1

LIS lengths: [1] -> [2] -> [1] -> [] -> [] -> [] -> [] -> []

Why: 9 cannot extend any previous increasing subsequence

Step 4: Check 33: greater than 10, 22, and 9; max LIS is max(1+1, 2+1, 1+1) = 3

LIS lengths: [1] -> [2] -> [1] -> [3] -> [] -> [] -> [] -> []

Why: 33 extends the longest subsequence ending at 22

Step 5: Check 21: greater than 10 and 9 but less than 22 and 33; max LIS is max(1+1, 1+1) = 2

LIS lengths: [1] -> [2] -> [1] -> [3] -> [2] -> [] -> [] -> []

Why: 21 extends subsequences ending at 10 or 9

Step 6: Check 50: greater than all previous; max LIS is max(1+1, 2+1, 1+1, 3+1, 2+1) = 4

LIS lengths: [1] -> [2] -> [1] -> [3] -> [2] -> [4] -> [] -> []

Why: 50 extends the longest subsequence ending at 33

Step 7: Check 41: greater than 10, 22, 9, 33, 21 but less than 50; max LIS is max(1+1, 2+1, 1+1, 3+1, 2+1) = 4

LIS lengths: [1] -> [2] -> [1] -> [3] -> [2] -> [4] -> [4] -> []

Why: 41 extends the longest subsequence ending at 33

Step 8: Check 60: greater than all previous; max LIS is max(1+1, 2+1, 1+1, 3+1, 2+1, 4+1, 4+1) = 5

LIS lengths: [1] -> [2] -> [1] -> [3] -> [2] -> [4] -> [4] -> [5]

Why: 60 extends the longest subsequence ending at 50 or 41

Result:

LIS lengths: [1] -> [2] -> [1] -> [3] -> [2] -> [4] -> [4] -> [5]
Longest Increasing Subsequence length = 5

Annotated Code

DSA C#

using System;

class LongestIncreasingSubsequence
{
    public static int FindLISLength(int[] nums)
    {
        int n = nums.Length;
        if (n == 0) return 0;

        int[] lis = new int[n];
        for (int i = 0; i < n; i++) lis[i] = 1; // each element alone is length 1

        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[i] > nums[j] && lis[i] < lis[j] + 1)
                {
                    lis[i] = lis[j] + 1; // extend subsequence ending at j
                }
            }
        }

        int maxLIS = 1;
        for (int i = 0; i < n; i++)
        {
            if (lis[i] > maxLIS) maxLIS = lis[i]; // find max length
        }
        return maxLIS;
    }

    static void Main()
    {
        int[] input = {10, 22, 9, 33, 21, 50, 41, 60};
        int result = FindLISLength(input);
        Console.WriteLine("Longest Increasing Subsequence length = " + result);
    }
}

for (int i = 0; i < n; i++) lis[i] = 1;

initialize LIS length for each element as 1

for (int i = 1; i < n; i++)

iterate over each element from second to last

for (int j = 0; j < i; j++)

check all previous elements to find smaller ones

if (nums[i] > nums[j] && lis[i] < lis[j] + 1)

if current element can extend LIS ending at j, update lis[i]

lis[i] = lis[j] + 1;

extend LIS length by 1

if (lis[i] > maxLIS) maxLIS = lis[i];

track maximum LIS length found

Output

Longest Increasing Subsequence length = 5

Complexity Analysis

Time: O(n^2) because for each element we check all previous elements to update LIS length

Space: O(n) because we store LIS length for each element in an array

vs Alternative: This dynamic programming approach is faster than checking all subsequences (which is exponential), but slower than advanced O(n log n) methods that use binary search

Edge Cases

empty array

returns 0 because no subsequence exists

DSA C#

if (n == 0) return 0;

array with all equal elements

returns 1 because longest increasing subsequence is any single element

DSA C#

for (int i = 0; i < n; i++) lis[i] = 1;

strictly decreasing array

returns 1 because no element can extend previous ones

DSA C#

if (nums[i] > nums[j] && lis[i] < lis[j] + 1)

When to Use This Pattern

When you see a problem asking for the longest sequence that increases step by step, think of the Longest Increasing Subsequence pattern using dynamic programming to build solutions from smaller parts.

Common Mistakes

Mistake: Updating LIS length without checking if it improves the current value
Fix: Add condition lis[i] < lis[j] + 1 before updating lis[i]

Mistake: Not initializing LIS array with 1 for each element
Fix: Initialize all lis[i] to 1 because each element alone is a subsequence

Summary

Finds the length of the longest increasing subsequence in an array.

Use when you need the longest ordered sequence that grows step by step inside a list.

Remember to build the solution by extending smaller subsequences and keep track of the best length at each step.

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