StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>You indeed can use dynamic programming approach here. For sake of simplicity , assume we need to find only the maximal length of such sequence <strong>seq</strong> (it will be easy to tweak solution to find the sequence itself).</p> <p>For each index we will store 2 values: </p> <ul> <li>maximal length of alternating sequence ending at that element where last step was increasing (say, <strong>incr</strong>[i])</li> <li>maximal length of alternating sequence ending at that element where last step was decreasing (say, <strong>decr</strong>[i])</li> </ul> <p>also by definition we assume <code>incr[0] = decr[0] = 1</code></p> <p>then each incr[i] can be found recursively:</p> <pre><code>incr[i] = max(decr[j])+1, where j < i and seq[j] < seq[i] decr[i] = max(incr[j])+1, where j < i and seq[j] > seq[i] </code></pre> <p>Required length of the sequence will be the maximum value in both arrays, complexity of this approach is O(N*N) and it requires 2N of extra memory (where N is the length of initial sequence)</p> <p>simple example in c:</p> <pre><code>int seq[N]; // initial sequence int incr[N], decr[N]; ... // Init sequences, fill incr and decr with 1's as initial values for (int i = 1; i < N; ++i){ for (int j = 0; j < i; ++j){ if (seq[j] < seq[i]) { // handle "increasing" step - need to check previous "decreasing" value if (decr[j]+1 > incr[i]) incr[i] = decr[j] + 1; } if (seq[j] > seq[i]) { if (incr[j]+1 > decr[i]) decr[i] = incr[j] + 1; } } } ... // Now all arrays are filled, iterate over them and find maximum value </code></pre> <p>How algorithm will work:</p> <p><strong>step 0</strong> (initial values):</p> <pre><code>seq = 7 4 8 9 3 5 2 1 incr = 1 1 1 1 1 1 1 1 decr = 1 1 1 1 1 1 1 1 </code></pre> <p><strong>step 1</strong> take value at index 1 ('4') and check previous values. 7 > 4 so we make "decreasing step from index 0 to index 1, new sequence values:</p> <pre><code>incr = 1 1 1 1 1 1 1 1 decr = 1 2 1 1 1 1 1 1 </code></pre> <p><strong>step 2.</strong> take value 8 and iterate over previous value:</p> <p>7 < 8, make increasing step: incr[2] = MAX(incr[2], decr[0]+1):</p> <pre><code>incr = 1 1 2 1 1 1 1 1 decr = 1 2 1 1 1 1 1 1 </code></pre> <p>4 < 8, make increasing step: incr[2] = MAX(incr[2], decr[1]+1):</p> <pre><code>incr = 1 1 3 1 1 1 1 1 decr = 1 2 1 1 1 1 1 1 </code></pre> <p>etc...</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