Longest Decreasing Subsequence using Dynamic Programming

In this problem (Longest Decreasing Subsequence), you are given an array of length N. You have to find the longest decreasing subsequence (LDS) from the given array. The longest decreasing subsequence problem is to find a sequence in which the subsequence's elements are in highest to lowest order and the subsequence is as long as possible. We will try to solve this problem using Dynamic Programming which will take O(n²) time complexity.

For example, consider below subsequence

[15, 27, 14, 38, 63, 55, 46, 65, 85]

Longest Decreasing Subsequence is [63, 55, 46] which has length 3.

Longest Decreasing Subsequence in an array cannot be always unique but in this question we have to give the length of the LDS.

Brute force approach

We can use recursion to solve this problem. For each element, there are two possibilities:-

• We exclude current item from LDS and recur for remaining items.
• We include current element in LDS if it is smaller than the previous element in LDS and recur for remaining items.

Finally, we return maximum value we get by including or excluding current element. The base case of the recursion would be when no element is left.

This approach will take exponential time complexity.

When we draw the recursion tree of the above approach then we can see the same subproblem is solved over and over again which exhibits the overlapping subproblem. And it also have optimal substructure as we can divide the problem into smaller subproblem until we get the trivial solution.

Better approach (using Dynamic Programming)

We know that the overlapping subproblem and optimal substructure problems can be solved by using Dynamic Programming. We will Memoized the subproblem solution rather than solving it again and again. Memoization will make use of the Top-Down approach since we break the problem in smaller sub-problem and then calculate the final result.

We can also solve this problem in bottom-up manner. In the bottom-up approach, we solve smaller sub-problems first, then solve larger sub-problems from them. The following bottom-up approach computes dp[i], for each 0 <= i < n, which stores the length of the longest decreasing subsequence of subarray arr[0..i] that ends with arr[i]. To calculate dp[i], we consider LDS of all smaller values of i(say j) already computed and pick the maximum dp[j] where arr[j] is more than the current element arr[i]. It has the same run-time as Memoization but no recursion overhead. The base-case for bottom-up approach is that, for first element of array the LDS of it is 1 (LDS of 1st element is itself).

Implementation in C++

Following is our C++ implementation of solving the Longest Decreasing Subsequence problem using Dynamic Programming:

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// Function to find length of LONGEST DECREASING SUBSEQUENCE
// of given array
int LDS(int arr[], int n) {
    // DP vector to store sub-problem solution. dp[i] stores the length
    // of the longest decreasing subsequence ends with arr[i]
    vector<int> dp(n);
    
    // to maintain the overall LDS of the array
    int overallMaxLDS= 0;
    
    for(int i= 0; i< dp.size(); i++) {
        int max= 0;     // this will calculate the length of maximum LDS upto ith element
        
        // do for each element in subarray arr[0..i-1]
        for(int j= 0; j< i; j++) {
            // find longest decreasing subsequence that ends with arr[j]
            // where arr[j] is more than the current element arr[i]
            if(arr[j] > arr[i]) {
                if(dp[j] > max)
                    max= dp[j];
            }
        }
        // LDS of ith element is max LDS upto i + 1 (include arr[i] in LDS)
        dp[i]= max + 1;
        
        // to maintain overall LDS of the array
        if(dp[i] > overallMaxLDS)
            overallMaxLDS= dp[i];
    }
    
    return overallMaxLDS;
}

// Driver Code
int main()
{
    int arr[] = {15, 27, 14, 38, 63, 55, 46, 65, 85};
    int n = sizeof(arr)/sizeof(arr[0]);
 
    cout << "Length of LDS is: " << LDS(arr, n);
 
    return 0;
}

Output:
Length of LDS is: 3

Workflow of solution

Suppose we have array [15, 27, 14, 38, 63, 55, 46, 65, 85] and we have to print length of length of Longest Decreasing Subsequence using Dynamic Programming.

• We will define a dp array of same size as that of the array. And at ith index of dp array we will store the length of LDS that ends with arr[i].
• For tabulation of DP we will first solve the smaller subproblem and travel till nth element to calculate the LDS of the array.
• Suppose we have to fill the dp[3] (LDS till 3rd element). Now, we will see what all elements are greater that arr[3] from arr[0 to 2] and maintain the max that will maintain the maximum length of LDS from dp array. It will check if (arr[j] > arr[i]) means the decreasing order is there and max will keep the maximum length LDS from dp.
• max will help us to get the max LDS of the number that are greater than arr[i]. After the maximum LDS is calculated that follows the decreasing order upto 38, which comes out to be 0 as no element is greater than 38. Therefore, we include 38 itself in its LDS. Because upto 38 no element follow LDS but LDS that ends at 38 is only of length 1.
• We have to calculate the LDS of whole array therefore we maintain the overallMaxLDS that store the length of LDS from the whole array.
• The dp array after the complete iteration looks like [1, 1, 2, 1, 1, 2, 3, 1, 1]. You can notice that dp[3] is 1 which denotes that LDS that ends at arr[3] (38) is of length 1. But the overall LDS of the array is of length 3 ([63, 55, 46]).

Time Complexity

The time complexity of the Dynamic Programming implementation of the Longest Decreasing Subsequence problem is O(n²) and space complexity used by it is O(n).