Find the longest subsequence of a given array such that all elements of the subsequence are sorted in increasing order – Dynamic Programming

The Longest Increasing Subsequence (LIS) problem is a classical problem in dynamic programming. Our goal is to find the length of the longest subsequence in an array where the elements are in strictly increasing order.

Problem Explanation

Given an array arr[] of size n, we need to find the length of the longest subsequence such that all elements of the subsequence are sorted in increasing order.

Example

  • Input: arr[] = [10, 22, 9, 33, 21, 50, 41, 60, 80]
  • Output: 6 (The LIS is [10, 22, 33, 50, 60, 80])

Approach

We’ll solve this problem using dynamic programming. The key observation is that the solution for a given element depends on the solutions to the previous elements in the array.

Steps:

  1. Create a DP array (dp[]) where each element dp[i] represents the length of the longest increasing subsequence that ends at index i.
  2. Initialize the DP array with 1 for all elements because the minimum subsequence length ending at any element is 1 (the element itself).
  3. For each element in the array (starting from the second element), check all previous elements to see if a valid increasing subsequence can be formed. If arr[j] < arr[i], update dp[i] = max(dp[i], dp[j] + 1) because we can append the current element arr[i] to the increasing subsequence ending at arr[j].
  4. After processing all elements, the maximum value in the dp[] array will be the length of the longest increasing subsequence.

Code

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

    # Base case: if array is empty
    if n == 0:
        return 0

    # Step 1: Create a dp array and initialize it with 1
    dp = [1] * n

    # Step 2: Fill dp array by comparing each element with previous ones
    for i in range(1, n):
        for j in range(0, i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    # Step 3: The length of the longest increasing subsequence is the maximum value in dp array
    lis_length = max(dp)

    # Step 4: Recovering the actual LIS sequence (Optional)
    lis_sequence = []
    current_length = lis_length

    # Traverse the dp array from the end to the start to find the actual sequence
    for i in range(n - 1, -1, -1):
        if dp[i] == current_length:
            lis_sequence.append(arr[i])
            current_length -= 1

    # Reverse the sequence since we collected it in reverse order
    lis_sequence.reverse()

    # Returning both the length and the actual LIS
    return lis_length, lis_sequence

# Test the function
arr = [10, 22, 9, 33, 21, 50, 41, 60, 80]
length, sequence = longest_increasing_subsequence(arr)

print("Length of LIS:", length)
print("LIS sequence:", sequence)

Explanation of the Code

  1. Input and Edge Case Handling:
  • We first check if the array is empty, in which case the LIS length would be 0.
  1. Initialization:
  • We create a dp[] array initialized to 1 for all elements. This is because every element on its own is an increasing subsequence of length 1.
  1. Filling the DP Array:
  • We iterate over each element arr[i] starting from the second element.
  • For each element arr[i], we check all previous elements arr[j] (where j < i). If arr[j] < arr[i], we update the dp[i] as dp[i] = max(dp[i], dp[j] + 1). This means that we can append the current element arr[i] to the subsequence ending at arr[j] and extend its length by 1.
  1. Finding the Maximum LIS Length:
  • After filling the dp[] array, the maximum value in dp[] gives us the length of the LIS.
  1. Recovering the Actual Sequence (Optional):
  • To reconstruct the LIS sequence, we start from the end of the dp[] array and trace back using the LIS length. We collect the elements that form the LIS in reverse order and then reverse the sequence at the end.
See also  Given a set of points in the plane, find the smallest convex polygon that encloses all points.

Time Complexity

The time complexity of this approach is O(n^2) because we have two nested loops: one to pick each element arr[i] and another to compare it with all previous elements arr[j]. The space complexity is O(n) due to the dp[] array.

Output

For the input arr = [10, 22, 9, 33, 21, 50, 41, 60, 80], the output will be:

Length of LIS: 6
LIS sequence: [10, 22, 33, 50, 60, 80]

Optimized Solution (Binary Search Approach)

The optimized solution for the Longest Increasing Subsequence (LIS) problem uses a combination of binary search and a greedy approach. This algorithm runs in O(n log n), which is much faster than the dynamic programming approach with O(n²) complexity.

Key Idea

The key idea is to maintain a tail array (or list) where:

  • Each element in tail[] represents the smallest possible ending value of an increasing subsequence of a particular length.

We can efficiently find the position where a new element should be inserted into this tail array using binary search.

Steps:

  1. Initialize an empty tail array (tail[]).
  2. For each element in the input array arr[], use binary search to find its correct position in tail[]. The position is determined by finding the smallest element in tail[] that is greater than or equal to the current element.
  3. Update the tail array:
  • If the current element can extend the largest subsequence so far, append it to tail[].
  • Otherwise, replace the element in tail[] with the current element to maintain the smallest possible ending element for a subsequence of that length.
  1. The length of the tail[] array will give the length of the longest increasing subsequence.
See also  write a program that will find how you can gain the most with a combination of buy-sell trades

Code (Optimized Solution)

import bisect

def longest_increasing_subsequence_optimized(arr):
    # Step 1: Initialize an empty tail array
    tail = []

    # Step 2: Iterate through the array
    for num in arr:
        # Step 3: Find the position where the current element should be placed
        pos = bisect.bisect_left(tail, num)

        # Step 4: If num is greater than all elements in tail, append it
        if pos == len(tail):
            tail.append(num)
        else:
            # Otherwise, replace the existing element to maintain the minimum possible value
            tail[pos] = num

    # Step 5: The length of the tail array is the length of the LIS
    return len(tail), tail

# Test the function
arr = [10, 22, 9, 33, 21, 50, 41, 60, 80]
length, tail_sequence = longest_increasing_subsequence_optimized(arr)

print("Length of LIS:", length)
print("Final tail sequence (not necessarily the LIS):", tail_sequence)

Explanation

  1. Binary Search with bisect_left:
  • We use bisect_left(tail, num) to find the index where num should be placed in tail[]. bisect_left finds the first position where num is greater than or equal to the elements in tail[].
  1. Updating the tail[] Array:
  • If the current number is larger than all elements in tail[], we append it (because it extends the LIS).
  • If the current number is smaller or equal to some elements in tail[], we replace the first element in tail[] that is greater than or equal to the current number. This replacement ensures that the tail[] array holds the smallest possible ending values for subsequences of different lengths.
  1. Length of LIS:
  • The size of the tail[] array at the end of the process will be the length of the LIS.
  1. Important Note:
  • The tail[] array does not store the actual LIS, but it helps to find the length of the LIS. The values in tail[] represent potential candidates for the smallest elements of increasing subsequences of different lengths.
See also  write a program that will find how you can gain the most with a single buy-sell-trade.

Example Walkthrough

Let’s walk through the array arr = [10, 22, 9, 33, 21, 50, 41, 60, 80] step by step:

  1. Start with an empty tail[].
  2. First element 10: Insert at position 0 → tail = [10]
  3. Next element 22: Insert at position 1 → tail = [10, 22]
  4. Next element 9: Insert at position 0 (replaces 10) → tail = [9, 22]
  5. Next element 33: Insert at position 2 → tail = [9, 22, 33]
  6. Next element 21: Insert at position 1 (replaces 22) → tail = [9, 21, 33]
  7. Next element 50: Insert at position 3 → tail = [9, 21, 33, 50]
  8. Next element 41: Insert at position 3 (replaces 50) → tail = [9, 21, 33, 41]
  9. Next element 60: Insert at position 4 → tail = [9, 21, 33, 41, 60]
  10. Last element 80: Insert at position 5 → tail = [9, 21, 33, 41, 60, 80]

At the end, the length of the tail[] is 6, which is the length of the LIS.

Time Complexity

  • Binary search using bisect_left takes O(log n), and we perform it for each element in the array, so the overall time complexity is O(n log n).
  • The space complexity is O(n) because we maintain the tail[] array.

Output

For the input arr = [10, 22, 9, 33, 21, 50, 41, 60, 80], the output will be:

Length of LIS: 6
Final tail sequence (not necessarily the LIS): [9, 21, 33, 41, 60, 80]

Key Takeaways

  • The tail[] array helps us to efficiently track potential LIS candidates, even though it doesn’t directly store the LIS.
  • The O(n log n) approach is much faster than the O(n²) dynamic programming approach, especially for large arrays.
facebookShare on Facebook
TwitterPost on X
FollowFollow us
PinterestSave

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *