Longest Increasing Subsequence 🎯

Welcome to our comprehensive guide on the Longest Increasing Subsequence (LIS)! This tutorial is designed to help both beginners and intermediates understand and master this important concept in the field of data structures and algorithms.

What is a Longest Increasing Subsequence? 📝

A Longest Increasing Subsequence (LIS) is a sequence in an array that is sorted in ascending order and has the maximum possible length. In other words, it's a sequence where no two elements are adjacent and where each element is greater than the previous one in the sequence.

Let's take a look at an example:

python

arr = [10, 22, 9, 33, 21, 50, 41, 60, 80]

The LIS for this array is [10, 22, 60, 80].

Why is the Longest Increasing Subsequence Important? 💡

The LIS problem is a fundamental one in computer science. It's used in various real-world applications, such as dynamic programming, optimization problems, and data compression. Understanding the LIS concept can help you excel in competitive programming and algorithmic challenges.

Finding the Longest Increasing Subsequence 📝

There are several algorithms to find the LIS in an array, but today we'll focus on the most common and efficient approach: Dynamic Programming.

The Dynamic Programming Approach 📝

Initialize an array lis of size equal to the input array arr. All elements of lis will initially be set to 1.

python

arr = [10, 22, 9, 33, 21, 50, 41, 60, 80]
lis = [1]*len(arr)

Iterate through the arr array. For each element arr[i], check the last element of the LIS ending before arr[i] and update the length if a longer LIS is found.

python

for i in range(1, len(arr)):
    for j in range(i):
        if arr[i] > arr[j] and len(lis[j]) > len(lis[i]):
            lis[i] = lis[j] + [arr[i]]

The final array lis now holds the lengths of the LIS ending at each position in the original array. The maximum length in this array is the length of the Longest Increasing Subsequence.

python

max_lis = max(lis)
print("The Longest Increasing Subsequence is:", max_lis, "[", arr[lis.index(max_lis)], "]")

Time and Space Complexity 📝

The time complexity of this algorithm is O(n^2), and the space complexity is O(n).

Practice Time 🎯

Now that you've learned the basics of the Longest Increasing Subsequence, it's time to test your skills!