Number of Longest Increasing Subsequence

Welcome to a fascinating journey into the world of Data Structures and Algorithms! Today, we'll dive deep into understanding the Longest Increasing Subsequence (LIS), a crucial concept in computer science. Let's get started!

What is an Increasing Subsequence? 📝

Before we dive into the longest one, let's first understand what an increasing subsequence is.

An increasing subsequence is a sequence of numbers within a larger sequence where every number is greater than or equal to the previous one.

For example, in the sequence [0, 8, 4, 12, 2, 10, 6], one such increasing subsequence is [0, 2, 6].

💡 Pro Tip: Remember, the order matters! The sequence [0, 2, 6] is different from [6, 2, 0].

Finding the Longest Increasing Subsequence 🎯

Now that we know what an increasing subsequence is, let's move on to the Longest Increasing Subsequence (LIS).

The Longest Increasing Subsequence (LIS) is the longest sequence of numbers in a larger sequence where every number is greater than or equal to the previous one.

Let's find the Longest Increasing Subsequence for the sequence [0, 8, 4, 12, 2, 10, 6].

Initially, let's assume that the LIS contains only one number, the smallest one. In our case, it's 0.
We then compare each remaining number in the sequence with the numbers in the LIS. If the number is greater than the last number in the LIS, we append it to the LIS. If not, we create a new LIS containing that number.
We repeat step 2 until there are no more numbers left to compare.

Applying this process to our sequence, we get the following LIS: [0, 8, 12, 10, 6].

The Longest Increasing Subsequence for [0, 8, 4, 12, 2, 10, 6] is [0, 8, 12, 10, 6] with a length of 5.

The Algorithm ✅

The process we just went through can be optimized to an algorithm called Dynamic Programming. Here's a simplified version of the Longest Increasing Subsequence algorithm:

python

def LIS(arr):
    n = len(arr)

    # Initialize LIS values for all indexes
    LIS = [1] * n

    # Compute optimized LIS values in bottom-up manner
    for i in range(1, n):
        for j in range(0, i):
            if arr[i] > arr[j] and LIS[i] < LIS[j] + 1:
                LIS[i] = LIS[j] + 1

    # Find the maximum value in LIS array
    max_value = max(LIS)

    return max_value

📝 Note: This Python function calculates the length of the Longest Increasing Subsequence for a given array of numbers.

Putting it into Practice 💡

Let's practice by finding the LIS for the following array: [50, 3, 10, 7, 40, 80].

python

arr = [50, 3, 10, 7, 40, 80]
print("The Length of the Longest Increasing Subsequence is: ", LIS(arr))

Wrapping Up 🎯

That's it for today! We learned about the Longest Increasing Subsequence, its importance, and an algorithm to find it.

With practice, you'll be able to solve more complex problems involving LIS. Keep coding, and remember, the journey to mastering Data Structures and Algorithms is a rewarding one!

Stay tuned for more enlightening lessons on CodeYourCraft. Happy learning! 🚀💻