# Longest Decreasing Subsequenceby Isai Damier, Android Engineer @ Google

```/***********************************************************************
* Author: Isai Damier
* Title: Longest Decreasing Subsequence
* Project: geekviewpoint
* Package: algorithms
*
* Statement:
*   Given a sequence of numbers, find a longest decreasing subsequence.
*
*
*  Time Complexity: O(n^2)
*
* Sample Input: {5,0,3,2,1,8}
* Sample Output: {5,3,2,1}
*
* DEFINITION OF SUBSEQUENCE:
*   A sequence is a particular order in which related objects follow
*   each other (e.g. DNA, Fibonacci). A sub-sequence is a sequence
*   obtained by omitting some of the elements of a larger sequence.
*
*   SEQUENCE       SUBSEQUENCE     OMISSION
*   {3,1,2,5,4}     {1,2}            3,5,4
*   {3,1,2,5,4}     {3,1,4}          2,5
*
*   SEQUENCE       NOT SUBSEQUENCE   REASON
*   {3,1,2,5,4}     {4,2,5}           4 should follow 5
*
* STRATEGY:
*   Illustrating by finding
*   a longest decreasing subsequence of {5,0,3,2,1,8}:
*
*   - Start by finding all subsequences of size 1: {5},{0},{3},{2},{1},{8};
*     each element is its own decreasing subsequence.
*
*   - Since we already have the solutions for the size 1 subsequences,
*     we can use them in solving for the size two subsequences. For
*     instance, we already know that 5 is the smallest element of a
*     decreasing subsequence of size 1, i.e. the subsequence {5}.
*     Therefore, all we need to get a subsequence of size 2 is add an
*     element smaller than 5 to {5}: {5,0}, {5,3}, {5,2}, {5,1};
*     {3,2}, {3,1}, {2,1}.
*
*   - Now we use the size 2 solutions to get the size 3 solutions:
*     {5,3,2}, {5,3,1}, {3,2,1}
*
*   - Then we use the size 3 solutions to get the size 4 solutions:
*     {5,3,2,1}. Since there are no size 5 solutions, we are done.
*
* SUMMARY:
*   Instead of directly solving the big problem, we solved a smaller
*   version and then 'copied and pasted' the solution of the subproblem
*   to find the solution to the big problem. To make the 'copy and paste'
*   part easy, we use a table (i.e. array) to track the subproblems
*   and their solutions. This strategy as a whole is called Dynamic
*   Programming. The tabling part is known as memoization, which means
*   writing memo.
*
*   To recognize whether you can use dynamic programming on a problem,
*   look for the following two traits: optimal substructures and
*   overlapping subproblems.
*
*   Optimal Substructures: the ability to 'copy and paste' the solution
*     of a subproblem plus an additional trivial amount of work so to
*     solve a larger problem. For example, we were able to use {5,3}
*     itself an optimal solution to the problem {5,0,3} to get {5,3,2}
*     as an optimal solution to the problem {5,0,3,2}.
*
*   Overlapping Subproblems: Okay. So in our approach the solution grew
*     from left to right: {5} to {5,3} to {5,3,2} etc. But in reality
*     we could have solved the problem using recursion trees so that
*     for example {5,3} could be reached either from {5} or from {3}.
*     That wouldn't really be a problem except we would be solving for
*     {5,3} more than once. Anytime a recursive solution would lead to
*     such overlaps, the bet is dynamic programming is the way to go.
*
*          {5}                 {3}
*         / | \               / | \
*        /  |  \             /  |  \
*       /   |   \           /   |   \
*   {5,0} {5,3} {5,2}   {5,3} {3,2} {3,1}
*
* NOTE:
* Dynamic Programming = Optimal Substructures + Overlapping Subproblems
* Divide and Conquer = Optimal Substructures - Overlapping Subproblems
*   see merge sort: http://www.geekviewpoint.com/java/sorting/mergesort
*
* Alternate coding: Not really much difference here, just another code
*   that some readers will find more intuitive:
*
*   int[] m = new int[A.length];
*   Arrays.fill(m, 1);
*
*   for(int x=1; x <A.length; x++)
*     for(int y = 0; y < x; y++)
*       if(m[y] >= m[x] && A[y] > A[x])
*         m[x]++;
*
*   int max = m[0];
*   for (int i = 0; i < m.length; i++)
*     if (max < m[i])
*       max = m[i];
*
*   List<Integer> result = new ArrayList<Integer>();
*   for (int i = m.length-1; i >=0 ; i--)
*     if (max == m[i]) {
*       max--;
*     }
*
*   Collections.reverse(result);
*   return result;
*
**********************************************************************/
package algorithm.programming.dynamic;

import java.util.ArrayList;
import java.util.List;

public class LongestDecreasingSubsequence {

public List<Integer> LDS(Integer[] A) {
int[] m = new int[A.length];
//Arrays.fill(m, 1);//not important here
for (int x = A.length - 2; x >= 0; x--) {
for (int y = A.length - 1; y > x; y--) {
if (m[x] <= m[y] && A[x] > A[y]) {
m[x]=m[y]+1;//or use m[x]++
}
}
}
int max = m[0];
for (int i = 0; i < m.length; i++) {
if (max < m[i]) {
max = m[i];
}
}
List<Integer> result = new ArrayList<Integer>();
for (int i = 0; i < m.length; i++) {
if (max == m[i]) {
max--;
}
}
return result;
}
}```
```package algorithm.programming.dynamic;

import java.util.Arrays;
import static org.junit.Assert.*;
import java.util.List;
import org.junit.Test;

public class LongestDecreasingSubsequenceTest {

@Test
public void testDecreasingSubsequence() {
Integer[] A = {1, 2, 3, 4, 5, 6, 7, 8, 9};
Integer[] B = {9, 8, 7, 6, 5, 4, 3, 2, 1};
Integer[] C = {15, 37, 12, 40, 8, 1, 44, 5, 3, 45, 2, 50};
Integer[] D = {15, 12, 8, 5, 3, 2};

LongestDecreasingSubsequence seq = new LongestDecreasingSubsequence();
List<Integer> actual = seq.LDS(A);
assertEquals(1, actual.size());
actual = seq.LDS(B);
assertTrue(Arrays.equals(B, actual.toArray(new Integer[0])));
actual = seq.LDS(C);
assertTrue(Arrays.equals(D, actual.toArray(new Integer[0])));
}
}```