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.
For example, consider below subsequence
[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
Longest decreasing subsequence is [12, 10, 9, 5, 3]
This subsequence has length 5; the input sequence has no 7-member decreasing subsequences.
The longest decreasing subsequence in this example is not unique: for instance,
[12, 10, 6, 5, 3] is another decreasing subsequences of equal length in the same input sequence.
We can use recursion to solve this problem. For each item, there are two possibilities –
2. We exclude current item from LDS and recurse for remaining items.
Finally, we return maximum value we get by including or excluding current item. The base case of the recursion would be when no items are left.
Below is C++ and Java implementation of the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <iostream> #include <climits> using namespace std; // Function to find length of longest decreasing subsequence int LDS(int arr[], int i, int n, int prev) { // Base case: nothing is remaining if (i == n) return 0; // case 1: exclude the current element and process the // remaining elements int excl = LDS(arr, i + 1, n, prev); // case 2: include the current element if it is smaller // than previous element in LDS int incl = 0; if (arr[i] < prev) incl = 1 + LDS(arr, i + 1, n, arr[i]); // return maximum of above two choices return max(incl, excl); } // main function int main() { int arr[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "Length of LDS is " << LDS(arr, 0, n, INT_MAX); return 0; } |
Output:
Length of LDS is 5
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
class Util { // Function to find length of longest decreasing subsequence // of given sub-array A[i..n) public static int LDS(int[] A, int i, int n, int prev) { // Base case: nothing is remaining if (i == n) { return 0; } // case 1: exclude the current element and process the // remaining elements int excl = LDS(A, i + 1, n, prev); // case 2: include the current element if it is smaller // than previous element in LDS int incl = 0; if (A[i] < prev) { incl = 1 + LDS(A, i + 1, n, A[i]); } // return maximum of above two choices return Integer.max(incl, excl); } // main function public static void main(String[] args) { int[] A = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 }; System.out.println("Length of LDS is " + LDS(A, 0, A.length, Integer.MAX_VALUE)); } } |
Output:
Length of LDS is 5
The time complexity of above solution is exponential and auxiliary space used by the program is O(1).
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. Above solution also exhibits overlapping subproblems. If we draw the recursion tree of the solution, we can see that the same sub-problems are getting computed again and again.
We know that problems having optimal substructure and overlapping subproblems can be solved by using Dynamic Programming, in which subproblem solutions are Memoized rather than computed again and again. 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 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 L[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 L[i], we consider LDS of all smaller values of i (say j) already computed and pick the maximum L[j] where arr[j] is more than the current element arr[i]. It has the same asymptotic run-time as Memoization but no recursion overhead.
Below is C++ and Java implementation of the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include <iostream> #include <climits> using namespace std; // Iterative function to find length of longest decreasing subsequence // of given array int LDS(int arr[], int n) { // array to store sub-problem solution. L[i] stores the length // of the longest decreasing subsequence ends with arr[i] int L[n] = { 0 }; // longest decreasing subsequence ending with arr[0] has length 1 L[0] = 1; // start from second element in the array for (int i = 1; i < n; i++) { // 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] && L[j] > L[i]) L[i] = L[j]; } // include arr[i] in LDS L[i]++; } // find longest decreasing subsequence (having maximum length) int lis = INT_MIN; for (int x : L) lis = max(lis, x); return lis; } // main function int main() { int arr[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 }; int n = sizeof(arr)/sizeof(arr[0]); cout << "Length of LDS is " << LDS(arr, n); return 0; } |
Output:
Length of LDS is 5
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
import java.util.Arrays; class LDS { // Iterative function to find length of longest decreasing subsequence // of given array public static int LDS(int[] A) { // array to store sub-problem solution. L[i] stores the length // of the longest decreasing subsequence ends with A[i] int[] L = new int[A.length]; // longest decreasing subsequence ending with A[0] has length 1 L[0] = 1; // start from second element in the array for (int i = 1; i < A.length; i++) { // do for each element in subarray A[0..i-1] for (int j = 0; j < i; j++) { // find longest decreasing subsequence that ends with A[j] // where A[j] is more than the current element A[i] if (A[j] > A[i] && L[j] > L[i]) { L[i] = L[j]; } } // include A[i] in LDS L[i]++; } // return longest decreasing subsequence (having maximum length) return Arrays.stream(L).max().getAsInt(); } // main function public static void main(String[] args) { int[] A = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 }; System.out.println("Length of LDS is " + LDS(A)); } } |
Output:
Length of LDS is 5
The time complexity of above solution is O(n2) and auxiliary space used by the program is O(n).
How to print LDS?
Above solutions only print the length of LDS but do not actually print LDS itself. To print the LDS, we actually have to store the longest decreasing subsequence in lookup table instead of storing just LDS length.
For example, consider below array
A[] = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
The Longest Decreasing Subsequence LDS[i] of subarray A[0..i] that ends with A[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
Below is C++ implementation of the idea:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include <iostream> #include <vector> using namespace std; // Iterative function to find longest decreasing subsequence // of given array void findLDS(int arr[], int n) { // LDS[i] stores the longest decreasing subsequence of sub-array // arr[0..i] that ends with arr[i] vector<int> LDS[n]; // LDS[0] denotes longest decreasing subsequence ending with arr[0] LDS[0].push_back(arr[0]); // start from second element in the array for (int i = 1; i < n; i++) { // 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] && LDS[j].size() > LDS[i].size()) LDS[i] = LDS[j]; } // include arr[i] in LDS[i] LDS[i].push_back(arr[i]); } // uncomment below lines to print contents of vector LDS /* for (int i = 0; i < n; i++) { cout << "LDS[" << i << "] - "; for (int j : LDS[i]) cout << j << " "; cout << endl; } */ // j will contain index of LDS int j = 0; for (int i = 0; i < n; i++) if (LDS[j].size() < LDS[i].size()) j = i; // print LDS for (int i : LDS[j]) cout << i << " "; } // main function int main() { int arr[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 }; int n = sizeof(arr)/sizeof(arr[0]); findLDS(arr, n); return 0; } |
Output:
12 10 6 5 3
The time complexity of above solution is O(n2) and auxiliary space used by the program is O(n2).
Thanks for reading.
Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply