The longest decreasing subsequence problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, highest to lowest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous or unique.

Please note that the problem specifically targets subsequences that need not be contiguous, i.e., subsequences are not required to occupy consecutive positions within the original sequences.

For example, consider the following subsequence:

[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

 
The longest decreasing subsequence is [12, 10, 9, 5, 3], which has length 5; the input sequence has no 6–member decreasing subsequences.

 
The longest decreasing subsequence in this example is not unique: for instance, [12, 10, 6, 5, 3] is another decreasing subsequence of equal length in the same input sequence.

Practice this problem

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

  1. Include the current item in LDS if it is smaller than the previous element in LDS and recur for the remaining items.
  2. Exclude the current item from LDS and recur for the remaining items.

Finally, return the maximum value we get by including or excluding the current item. The base case of the recursion would be when no items are left. Following is the C++, Java, and Python implementation of the idea:

C++


Download  Run Code

Output:

The length of the LDS is 5

Java


Download  Run Code

Output:

The length of the LDS is 5

Python


Download  Run Code

Output:

The length of the LDS is 5

The time complexity of the above solution is exponential and occupies space in the call stack.
 

 
The problem has an optimal substructure. That means the problem can be broken down into smaller, simple “subproblems”, which can further be divided into yet simpler, smaller subproblems until the solution becomes trivial. The above solution also exhibits overlapping subproblems. If we draw the solution’s recursion tree, we can see that the same subproblems are repeatedly computed.

We know that problems with optimal substructure and overlapping subproblems can be solved using dynamic programming, where subproblem solutions are memoized rather than computed repeatedly. The memoized version follows the top-down approach since we first break the problem into subproblems and then calculate and store values.

 
We can also solve this problem in a bottom-up manner. In the bottom-up approach, we solve smaller subproblems first, then solve larger subproblems from them. The following bottom-up approach computes L[i], for each 0 <= i < n, which stores the length of the longest decreasing subsequence of subarray nums[0…i] that ends with nums[i]. To calculate L[i], consider LDS of all smaller values of i (say j) already computed and pick the maximum L[j], where nums[j] is more than the current element nums[i]. It has the same asymptotic runtime as Memoization but no recursion overhead.

Following is the C++, Java, and Python implementation of the idea:

C++


Download  Run Code

Output:

The length of the LDS is 5

Java


Download  Run Code

Output:

The length of the LDS is 5

Python


Download  Run Code

Output:

The length of the LDS is 5

The time complexity of the above solution is O(n2) and requires O(n) extra space, where n is the size of the given sequence.

How to print LDS?

The above-discussed methods only print the length of LDS but do not print LDS itself. To print the LDS, we have to store the longest decreasing subsequence in the lookup table instead of storing just the LDS length.

 
For example, consider the following array:

nums[] = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

The longest decreasing subsequence LDS[i] of subarray nums[0…i] that ends with nums[i] are:

LDS[0] — 0
LDS[1] — 8
LDS[2] — 8 4
LDS[3] — 12
LDS[4] — 8 4 2
LDS[5] — 12 10
LDS[6] — 12 10 6
LDS[7] — 14
LDS[8] — 8 4 2 1
LDS[9] — 12 10 9
LDS[10] — 12 10 6 5
LDS[11] — 14 13
LDS[12] — 12 10 6 5 3
LDS[13] — 14 13 11
LDS[14] — 12 10 9 7
LDS[15] — 15

The algorithm can be implemented as follows in C++, Java, and Python:

C++


Download  Run Code

Output:

12 10 6 5 3

Java


Download  Run Code

Output:

[12, 10, 6, 5, 3]

Python


Download  Run Code

Output:

[12, 10, 6, 5, 3]

The time complexity of the above solution is O(n2) and requires O(n2) extra space, where n is the size of the given sequence.