Longest Increasing Subsequence in DSA C

Mental Model

Find the longest chain of numbers that keep going up without breaking the order. We want the longest list where each number is bigger than the one before.

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

Array: [10] -> [22] -> [9] -> [33] -> [21] -> [50] -> [41] -> [60]
LIS: 10 -> 22 -> 33 -> 50 -> 60 -> null

Dry Run Walkthrough

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

Goal: Find the length and elements of the longest increasing subsequence

Step 1: Initialize LIS lengths array with 1 for each element

arr: 10 -> 22 -> 9 -> 33 -> 21 -> 50 -> 41 -> 60
LIS: 1 -> 1 -> 1 -> 1 -> 1 -> 1 -> 1 -> 1

Why: Each element alone is a subsequence of length 1

Step 2: Check element 22: compare with 10, update LIS if 22 > 10

LIS: 1 -> 2 -> 1 -> 1 -> 1 -> 1 -> 1 -> 1

Why: 22 is bigger than 10, so LIS ending at 22 is 2

Step 3: Check element 9: compare with 10 and 22, no update since 9 < both

LIS: 1 -> 2 -> 1 -> 1 -> 1 -> 1 -> 1 -> 1

Why: 9 is smaller, so LIS length remains 1

Step 4: Check element 33: update LIS comparing with 10, 22, 9

LIS: 1 -> 2 -> 1 -> 3 -> 1 -> 1 -> 1 -> 1

Why: 33 > 22, so LIS ending at 33 is 3

Step 5: Check element 21: update LIS comparing with previous elements

LIS: 1 -> 2 -> 1 -> 3 -> 2 -> 1 -> 1 -> 1

Why: 21 > 10 but < 22, so LIS ending at 21 is 2

Step 6: Check element 50: update LIS comparing with all previous elements

LIS: 1 -> 2 -> 1 -> 3 -> 2 -> 4 -> 1 -> 1

Why: 50 > 33, so LIS ending at 50 is 4

Step 7: Check element 41: update LIS comparing with previous elements

LIS: 1 -> 2 -> 1 -> 3 -> 2 -> 4 -> 4 -> 1

Why: 41 > 33, so LIS ending at 41 is 4

Step 8: Check element 60: update LIS comparing with all previous elements

LIS: 1 -> 2 -> 1 -> 3 -> 2 -> 4 -> 4 -> 5

Why: 60 > 50 and 41, so LIS ending at 60 is 5

Result:

Longest Increasing Subsequence length = 5
LIS array: 1 -> 2 -> 1 -> 3 -> 2 -> 4 -> 4 -> 5

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Function to find length of LIS
int longest_increasing_subsequence(int arr[], int n) {
    if (n == 0) return 0;
    int *lis = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        lis[i] = 1; // Initialize LIS length for each element
    }

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {
                lis[i] = lis[j] + 1; // Update LIS length if current element extends LIS
            }
        }
    }

    int max_lis = 0;
    for (int i = 0; i < n; i++) {
        if (lis[i] > max_lis) {
            max_lis = lis[i]; // Find maximum LIS length
        }
    }

    free(lis);
    return max_lis;
}

int main() {
    int arr[] = {10, 22, 9, 33, 21, 50, 41, 60};
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = longest_increasing_subsequence(arr, n);
    printf("Longest Increasing Subsequence length = %d\n", result);
    return 0;
}

lis[i] = 1; // Initialize LIS length for each element

Set each element's LIS length to 1 as base case

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

Check if current element can extend LIS ending at j

lis[i] = lis[j] + 1; // Update LIS length if current element extends LIS

Update LIS length for i if longer subsequence found

if (lis[i] > max_lis) {

Track maximum LIS length found so far

Output

Longest Increasing Subsequence length = 5

Complexity Analysis

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

Space: O(n) for the LIS array that stores length of subsequence ending at each element

vs Alternative: Naive approach tries all subsequences with exponential time; this DP approach is much faster but still quadratic

Edge Cases

empty array

returns 0 since no subsequence exists

DSA C

int longest_increasing_subsequence(int arr[], int n) { if (n == 0) return 0; ... }

array with all equal elements

returns 1 since only single elements form increasing subsequences

DSA C

lis[i] = 1; // Initialize LIS length for each element

strictly decreasing array

returns 1 since no increasing pairs exist

DSA C

if (arr[i] > arr[j] && lis[i] < lis[j] + 1) { lis[i] = lis[j] + 1; }

When to Use This Pattern

When you see a problem asking for the longest increasing order in a sequence, use the Longest Increasing Subsequence pattern because it finds the longest chain of increasing elements efficiently.

Common Mistakes

Mistake: Not initializing LIS array with 1 for each element
Fix: Initialize each LIS length to 1 because each element alone is a subsequence

Mistake: Updating LIS length without checking if current element is greater than previous
Fix: Add condition arr[i] > arr[j] before updating LIS length

Mistake: Not tracking maximum LIS length after filling LIS array
Fix: Iterate LIS array to find and return the maximum value

Summary

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

Use when you need the longest ordered chain of increasing numbers from a sequence.

Remember to build LIS lengths by comparing each element with all previous elements and updating lengths accordingly.

Practice

1. What does the Longest Increasing Subsequence (LIS) problem ask you to find in a sequence of numbers?

easy

A. The longest subsequence where each number is larger than the previous one

B. The longest subsequence where each number is smaller than the previous one

C. The longest subsequence where numbers are equal

D. The shortest subsequence with increasing numbers

Solution

1. Step 1: Understand the LIS definition

   The Longest Increasing Subsequence is a subsequence where every next number is strictly greater than the previous one.

2. Step 2: Compare options with the definition

   The longest subsequence where each number is larger than the previous one matches the definition exactly. Options B, C, and D do not describe LIS correctly.

3. Final Answer:

   The longest subsequence where each number is larger than the previous one -> Option A

4. Quick Check:

   LIS = longest increasing subsequence [OK]

Hint: LIS means strictly increasing sequence, not equal or decreasing [OK]

Common Mistakes:

• Confusing increasing with non-decreasing
• Thinking LIS means equal numbers
• Mixing up subsequence with substring

2. Which of the following C code snippets correctly initializes the array to store LIS lengths for each element in an array arr of size n?

easy

A. int lis[n] = {0};

B. int lis[n]; for(int i=0; i

C. int lis[n]; for(int i=0; i

D. int lis[n]; memset(lis, 1, n*sizeof(int));

Solution

1. Step 1: Understand LIS initialization

   Each element starts with LIS length 1 because each element alone is a subsequence.

2. Step 2: Check code correctness

   int lis[n]; for(int i=0; i

3. Final Answer:

   int lis[n]; for(int i=0; i -> Option B

4. Quick Check:

   Initialize LIS array with 1 [OK]

Hint: Initialize LIS array elements to 1, not 0 [OK]

Common Mistakes:

• Using memset to set integers to 1 (wrong)
• Initializing LIS array with zeros
• Not initializing LIS array at all

3. What is the output of the following C code snippet that calculates the length of LIS for array arr = {10, 22, 9, 33, 21, 50, 41, 60}?

int arr[] = {10, 22, 9, 33, 21, 50, 41, 60};
int n = 8;
int lis[8];
for(int i=0; i arr[j] && lis[i] < lis[j] + 1) {
      lis[i] = lis[j] + 1;
    }
  }
}
int max = lis[0];
for(int i=1; i max) max = lis[i];
}
printf("%d", max);

medium

A. 4

B. 6

C. 5

D. 3

Solution

1. Step 1: Calculate LIS values step-by-step

   Start with lis = {1,1,1,1,1,1,1,1} - i=1: arr[1]=22 > arr[0]=10, lis[1]=max(1,1+1)=2 - i=2: arr[2]=9 no smaller than previous, lis[2]=1 - i=3: arr[3]=33 > 22 and 10, lis[3]=max(1,2+1)=3 - i=4: arr[4]=21 > 10 but <22, lis[4]=max(1,1+1)=2 - i=5: arr[5]=50 > 33, 22, 21, lis[5]=max(1,3+1)=4 - i=6: arr[6]=41 > 33, 22, 21, lis[6]=max(1,3+1)=4 - i=7: arr[7]=60 > 50, 41, lis[7]=max(1,4+1)=5

2. Step 2: Find maximum LIS length

   Maximum value in lis array is 5.

3. Final Answer:

   5 -> Option C

4. Quick Check:

   LIS length for given array = 5 [OK]

Hint: Trace LIS array updates carefully for each element [OK]

Common Mistakes:

• Counting non-increasing subsequences
• Forgetting to update lis[i] only if condition met
• Mixing up indices in nested loops

4. Identify the bug in the following C code snippet that attempts to compute the LIS length:

int arr[] = {3, 10, 2, 1, 20};
int n = 5;
int lis[5];
for(int i=0; i arr[j] && lis[i] < lis[j] + 1) {
      lis[i] = lis[j] + 1;
    }
  }
}
int max = lis[0];
for(int i=1; i max) max = lis[i];
}
printf("%d", max);

medium

A. LIS array should be initialized with 1, not 0

B. The nested loops should start from i=0

C. The condition arr[i] > arr[j] should be arr[i] >= arr[j]

D. The max variable should be initialized to 0

Solution

1. Step 1: Check LIS array initialization

   LIS array elements represent length of subsequence ending at each index. Each element alone forms subsequence of length 1, so initialize lis[i] = 1.

2. Step 2: Analyze effect of initialization

   Initializing lis[i] = 0 causes all comparisons lis[i] < lis[j] + 1 to fail or produce wrong results, leading to incorrect max LIS length.

3. Final Answer:

   LIS array should be initialized with 1, not 0 -> Option A

4. Quick Check:

   Initialize LIS array with 1 to avoid zero-length subsequences [OK]

Hint: Always start LIS lengths at 1, not 0 [OK]

Common Mistakes:

• Initializing LIS array with zeros
• Changing comparison operators incorrectly
• Starting loops at wrong indices

5. Given an array arr = {5, 7, 4, 8, 6, 9}, write a C function to find the length of the Longest Increasing Subsequence using dynamic programming. What is the length of the LIS for this array?

hard

A. 6

B. 3

C. 5

D. 4

Solution

1. Step 1: Initialize LIS array with 1 for each element

   lis = {1,1,1,1,1,1}

2. Step 2: Update LIS values by comparing each element with previous ones

   - i=1 (7): 7 > 5, lis[1] = max(1, 1+1) = 2 - i=2 (4): 4 > 5? No, lis[2] = 1 - i=3 (8): 8 > 5, lis[3] = max(1,1+1)=2; 8 > 7, lis[3] = max(2,2+1)=3; 8 > 4, lis[3] = max(3,1+1)=3 - i=4 (6): 6 > 5, lis[4] = max(1,1+1)=2; 6 > 7? No; 6 > 4, lis[4] = max(2,1+1)=2; 6 > 8? No - i=5 (9): 9 > 5, lis[5] = max(1,1+1)=2; 9 > 7, lis[5] = max(2,2+1)=3; 9 > 4, lis[5] = max(3,1+1)=3; 9 > 8, lis[5] = max(3,3+1)=4; 9 > 6, lis[5] = max(4,2+1)=4

3. Step 3: Find maximum LIS length

   Maximum lis value is 4.

4. Final Answer:

   4 -> Option D

5. Quick Check:

   LIS length for given array = 4 [OK]

Hint: Update LIS by checking all previous smaller elements [OK]

Common Mistakes:

• Not updating LIS correctly for all previous elements
• Confusing subsequence with substring
• Forgetting to initialize LIS array with 1