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.