Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Chris's answer fails on the list [9,10,9], producing 10 instead of 9+9 = 18.</p> <p>Joe is not quite right. Traveling salesman requires you to visit every city, whereas there's no analog to that here.</p> <p>One possible solution would be the recursive solution:</p> <pre><code>function Max_route(A) if A's length = 1 A[0] else maximum of A[0]+Max_route(A[2...]) Max_route[1...] </code></pre> <p>This has the same big-O as a naive fibonacci function, and should yield to some of the same optimizations (e.g. memoization) if you care about efficiency in addition to simply getting a correct answer.</p> <p>-- MarkusQ</p> <p>[Edit] ---</p> <p>Because some people don't seem to be getting this, I want to explain what I meant by memoization and why it matters. </p> <p>You could wrap the function above so that it only computed the value for each array once (the first time it was called), and on subsequent calls would simply return the saved result. This would take O(n) space but would return in constant time. That means the whole algorithm would return in O(n) time, better than the exponential time of the less cluttered version above. I was assuming this was well understood.</p> <p>[Second edit]------------------------------</p> <p>If we expand the above a bit and tease it apart we get:</p> <pre><code>f [] :- [],0 f [x] :- [x],x f [a,b] :- if a &gt; b then [a],a else [b],b f [a,b,t] :- ft = f t fbt = f [b|t] if a + ft.sum &gt; fbt.sum [a|ft.path],a+ft.sum else fbt </code></pre> <p>Which we can unroll into a pseudo basic using only size n arrays of integers and booleans, and the operations of 1) array indexing and indexed array assignment, 2) integer math, including comparison, 3) if/then/else, and 4) one single loop of O(n):</p> <pre><code>dim max_sum_for_initial[n],next_to_get_max_of_initial[n],use_last_of_initial[n] max_sum_for_initial[0] = 0 next_to_get_max_of_initial[0] = -1 use_last_of_initial[0] = false max_sum_for_initial[1] = a[0] next_to_get_max_of_initial[1] = -1 use_last_of_initial[1] = true if a[0] &gt; a[1] max_sum_for_initial[2] = a[0] next_to_get_max_of_initial[2] = 0 use_last_of_initial[2] = false else max_sum_for_initial[2] = a[1] next_to_get_max_of_initial[1] = -1 use_last_of_initial[2] = true for i from 3 to n if a[i]+max_sum_for_initial[i-2] &gt; max_sum_for_initial[i-1] max_sum_for_initial[i] = a[i]+max_sum_for_initial[i-2] next_to_get_max_of_initial[i] = i-2 use_last_of_initial[i] = true else max_sum_for_initial[i] = max+sum_for_initial[i-1] next_to_get_max_of_initial[i] = i-1 use_last_of_initial[i] = false </code></pre> <p>At the end we can extract the results (in reverse order):</p> <pre><code>for i = n; i &gt;= 0; i = next_to_get_max_of_initial[i] if use_last_of_initial[i] then print a[i] </code></pre> <p>Note that what we just did manually is something that a good compiler for a modern language should be able to accomplish with tail recursion, memoization, etc.</p> <p>I hope that is clear enough.</p> <p>-- MarkusQ</p> <p>It's O(n).</p>
    singulars
    1. This table or related slice is empty.
    1. POAlgorithm to find the maximum subsequence of an array of positive numbers . Catch : No adjacent elements allowed
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USMarkusQ
    1. USMarkusQ
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COWhat is the linear algorithm you mentioned in comments? The fastest algorithm so far is @sth's one which is O(N**2) in time and O(N) in space. http://stackoverflow.com/questions/584228/algorithm-to-find-the-maximum-subsequence-of-an-array-of-positive-numbers-catch/584343#584343
      singulars
      1. PO
      1. USjfs
    2. CO@sth's is linear in time and space, as is this one with smart memoization.
      singulars
      1. PO
      1. USMarkusQ
    3. COYour algorithm is not linear. A naive recursive Fibonacci function and a more efficient iterative one use different algorithms. Could you give a link to an answer that contains O(N) algorithm (and not just references that it could be done in O(N)).
      singulars
      1. PO
      1. USjfs
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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