The Longest Increasing Subsequence (LIS) problem is a fundamental concept in dynamic programming that comes up frequently in interviews and competitive programming. Essentially, the goal is to identify the longest subsequence in a given sequence where the elements are sorted in increasing order. It’s a fascinating problem that helps in understanding how to approach complexity and optimize solutions.

What is a Subsequence?

Before diving into LIS, let's clarify what a subsequence is. A subsequence is a sequence derived from another sequence by deleting some or no elements without changing the order of the remaining elements. For example, consider the sequence:

A = [3, 10, 2, 1, 20]

Some valid subsequences of A are:

• [3, 10, 20]
• [3, 2, 1]
• [10, 20]

But [3, 1, 10] is not a subsequence since the order is not preserved.

Understanding LIS

The Longest Increasing Subsequence is one of the longest subsequences that can be formed such that all elements in it are sorted in increasing order. Using the earlier example, the LIS of the sequence A is [3, 10, 20], which has a length of 3.

Visualizing LIS

For a clearer understanding, let’s take the sequence again:

A = [3, 10, 2, 1, 20]

If we start examining potential increasing subsequences:

• Starting with 3, we can include 10 and 20.
• If we start with 2, the only larger number after 2 is 20, leading to [2, 20].
• Starting with 1, the longest subsequence remains [1, 20].

Ultimately, the longest subsequences we can form are [3, 10, 20] or [2, 20].

Approaches to Solve LIS

We can tackle the LIS problem in a few ways, but we’ll cover the two most common approaches: the DP approach and the Binary Search + Dynamic Programming approach.

DP Approach

This approach uses a dynamic programming table to store the length of the longest increasing subsequence ending at each index.

1. Initialization: Create a DP array where each index initially contains the value 1 (since the minimum LIS ending at an element is itself).

2. Filling the DP table: For every element in the input array:

   • For each preceding element, check if it’s less than the current element. If yes, update the DP table to take the maximum of its current value or the value at that index plus one.

Here’s the implementation:

def length_of_lis(nums):
    if not nums:
        return 0

    dp = [1] * len(nums)

    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

# Example
A = [3, 10, 2, 1, 20]
print(length_of_lis(A))  # Output: 3

The time complexity of this approach is O(n^2), where n is the number of elements in the input array.

Binary Search + DP Approach

This advanced technique helps reduce the time complexity to O(n log n) using a combination of dynamic programming and binary search. The key idea is to maintain an array where we store the smallest tail for all increasing subsequences.

1. Initialization: Create an empty list tails. This will store the smallest tail for all increasing subsequences.

2. Binary Search Logic: Iterate over each number in the list:

   • Use binary search to find the index of the smallest number in tails that is greater than or equal to the current number.
   • If found, replace it; if not, append the current number to tails.

Here's the implementation:

import bisect

def length_of_lis(nums):
    if not nums:
        return 0

    tails = []

    for num in nums:
        index = bisect.bisect_left(tails, num)
        if index == len(tails):
            tails.append(num)
        else:
            tails[index] = num
            
    return len(tails)

# Example
A = [3, 10, 2, 1, 20]
print(length_of_lis(A))  # Output: 3

Summary of Key Points

• The Longest Increasing Subsequence problem is classic in dynamic programming.
• The naive DP solution has a time complexity of O(n^2).
• The more efficient O(n log n) solution employs binary search to maintain a list of minimum end values.

Understanding and solving the Longest Increasing Subsequence problem not only showcases your algorithmic prowess but also builds a strong foundation in dynamic programming concepts that will be invaluable in tackling other challenges.