StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This is a dynamic programming problem. The idea is to evaluate every possible subsequence combination and store sub problem results in an array so you don't need to compute them twice.</p> <pre><code>public class LDS { /* For each item in the array, get the longest decreasing subsequence to that item. return the max subsequence to that item, adding 1 for the item itself. In both calculate and longestToN, subproblem results are stored and reused to avoid duplicate computation. */ public int calculate(int []arr) { int []table = new int[arr.length]; for (int i = 0; i < arr.length; ++i) { table[i] = -1; } int m = 0; for (int n = 0; n < arr.length; ++n) { if (table[n] == -1) {//Memoize table[n] = longestToN(n, arr, table); } m = Math.max(m, longestToN(n, arr, table)); } return m + 1; } /* Recursively finds the longest decreasing subsequence in array up until arr[n] inclusive. */ private int longestToN(int n, int []arr, int []table) { int m = 0; for (int i = n; i >= 0; --i) { if (arr[i] > arr[n]) { if (table[i] == -1) {//Memoize table[i] = longestToN(i, arr, table); } m = Math.max(m, 1 + table[i]); } } return m; } } </code></pre> <p>To run the code:</p> <pre><code> LDS lds = new LDS(); int []arr = {9, 4, 3, 2, 5, 4, 3, 2}; int ret = lds.calculate(arr); System.out.println("Longest decreasing subsequence is " + ret); </code></pre> <p>Running the code on your example input calculates 5. I recommend a book called the algorithm design manual for a better understanding of dynamic programming. The author is a professor and posts lectures from his algorithms online @ <a href="http://www.cs.sunysb.edu/~skiena/373/" rel="nofollow">http://www.cs.sunysb.edu/~skiena/373/</a>.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload