Databases
StackOverflow2013
Postsdbo
PO
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    text
    copied!<p>Here is how to simply find longest increasing/decreasing subsequence in Mathematica:</p> <pre><code> LIS[list_] := LongestCommonSequence[Sort[list], list]; input={0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}; LIS[input] -1*LIS[-1*input] </code></pre> <p>Output:</p> <pre><code>{0, 2, 6, 9, 11, 15} {12, 10, 9, 5, 3} </code></pre> <p>Mathematica has also <strong>LongestIncreasingSubsequence</strong> function in the <strong>Combinatorica`</strong> libary. If you do not have Mathematica you can query the <a href="http://www.wolframalpha.com/" rel="noreferrer">WolframAlpha</a>.</p> <blockquote> <h2>C++ O(nlogn) solution</h2> <p>There's also an O(nlogn) solution based on some observations. Let Ai,j be the smallest possible tail out of all increasing subsequences of length j using elements a<sub>1</sub>, a<sub>2</sub>, ... , a<sub>i</sub>. Observe that, for any particular i, A<sub>i,1</sub>, A<sub>i,2</sub>, ... , A<sub>i,j</sub>. This suggests that if we want the longest subsequence that ends with ai + 1, we only need to look for a j such that Ai,j &lt; ai + 1 &lt; = Ai,j + 1 and the length will be j + 1. Notice that in this case, Ai + 1,j + 1 will be equal to ai + 1, and all Ai + 1,k will be equal to Ai,k for k!=j+1. Furthermore, there is at most one difference between the set Ai and the set Ai + 1, which is caused by this search. Since A is always ordered in increasing order, and the operation does not change this ordering, we can do a binary search for every single a<sub>1</sub>, a<sub>2</sub>, ... , a<sub>n</sub>.</p> <h2>Implementation <a href="http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence.cpp" rel="noreferrer">C++</a> (O(nlogn) algorithm)</h2> <pre><code>#include &lt;vector&gt; using namespace std; /* Finds longest strictly increasing subsequence. O(n log k) algorithm. */ void find_lis(vector&lt;int&gt; &amp;a, vector&lt;int&gt; &amp;b) { vector&lt;int&gt; p(a.size()); int u, v; if (a.empty()) return; b.push_back(0); for (size_t i = 1; i &lt; a.size(); i++) { if (a[b.back()] &lt; a[i]) { p[i] = b.back(); b.push_back(i); continue; } for (u = 0, v = b.size()-1; u &lt; v;) { int c = (u + v) / 2; if (a[b[c]] &lt; a[i]) u=c+1; else v=c; } if (a[i] &lt; a[b[u]]) { if (u &gt; 0) p[i] = b[u-1]; b[u] = i; } } for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v; } /* Example of usage: */ #include &lt;cstdio&gt; int main() { int a[] = { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 }; vector&lt;int&gt; seq(a, a+sizeof(a)/sizeof(a[0])); vector&lt;int&gt; lis; find_lis(seq, lis); for (size_t i = 0; i &lt; lis.size(); i++) printf("%d ", seq[lis[i]]); printf("\n"); return 0; } </code></pre> </blockquote> <p>Source: <a href="http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence" rel="noreferrer">link</a></p> <p>I have rewritten the C++ implementation to Java a while ago, and can confirm it works. Vector alternative in python is List. But if you want to test it yourself, here is link for online compiler with example implementation loaded: <a href="http://www.ideone.com/oseBi" rel="noreferrer">link</a></p> <p>Example data is: <code>{ 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 }</code> and answer: <code>1 3 4 5 6 7</code>.</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