Longest Increasing Subsequence in DSA C - Build from Scratch

Longest Increasing Subsequence

📖 Scenario: Imagine you are analyzing a sequence of daily temperatures to find the longest period where the temperature keeps increasing day by day.

🎯 Goal: You will write a C program to find the length of the longest increasing subsequence (LIS) in a given array of integers.

📋 What You'll Learn

Create an integer array called arr with the exact values: 10, 22, 9, 33, 21, 50, 41, 60

Create an integer variable called n that stores the length of arr

Create an integer array called lis of the same length as arr

Use a for loop with variable i to initialize all elements of lis to 1

Use nested for loops with variables i and j to compute the LIS values

Create an integer variable called max_lis to track the maximum LIS length

Print the value of max_lis as the final output

💡 Why This Matters

🌍 Real World

Finding trends in data such as stock prices, temperatures, or sales figures where increasing sequences are important.

💼 Career

Understanding LIS helps in algorithm design, dynamic programming, and problem-solving skills required in software development and data analysis roles.

1

Create the input array and its length

Create an integer array called arr with these exact values: 10, 22, 9, 33, 21, 50, 41, 60. Then create an integer variable called n that stores the length of arr.

DSA C

#include 

int main() {
    // Create the array arr with values 10, 22, 9, 33, 21, 50, 41, 60
    // Create the integer n to store the length of arr
    // Your code here

    return 0;
}

Hint

Use sizeof(arr) / sizeof(arr[0]) to get the length of the array.

2

Initialize the LIS array

Create an integer array called lis of length n. Use a for loop with variable i from 0 to n - 1 to set all elements of lis to 1.

DSA C

#include 

int main() {
    int arr[] = {10, 22, 9, 33, 21, 50, 41, 60};
    int n = sizeof(arr) / sizeof(arr[0]);
    int lis[n];
    // Initialize all elements of lis to 1 using a for loop
    // Your code here

    return 0;
}

Hint

Use a for loop from 0 to n - 1 and set lis[i] = 1.

3

Compute the LIS values

Use nested for loops with variables i from 1 to n - 1 and j from 0 to i - 1. Inside the inner loop, if arr[i] > arr[j] and lis[i] < lis[j] + 1, update lis[i] to lis[j] + 1. Then create an integer variable called max_lis and set it to 1. Use a for loop with variable i from 0 to n - 1 to update max_lis to the maximum value in lis.

DSA C

#include 

int main() {
    int arr[] = {10, 22, 9, 33, 21, 50, 41, 60};
    int n = sizeof(arr) / sizeof(arr[0]);
    int lis[n];

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

    // Compute the LIS values using nested for loops
    // Create max_lis and find the maximum value in lis
    // Your code here

    return 0;
}

Hint

Use two loops to compare each pair of elements and update lis. Then find the maximum value in lis.

4

Print the length of the longest increasing subsequence

Use printf to print the value of max_lis with the exact format: "Length of LIS is %d\n".

DSA C

#include 

int main() {
    int arr[] = {10, 22, 9, 33, 21, 50, 41, 60};
    int n = sizeof(arr) / sizeof(arr[0]);
    int lis[n];

    for (int i = 0; i  arr[j] && lis[i]  max_lis) {
            max_lis = lis[i];
        }
    }

    // Print the length of the longest increasing subsequence
    printf("Length of LIS is %d\n", max_lis);

    return 0;
}

Hint

Use printf("Length of LIS is %d\n", max_lis); to print the result.