StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This problem can be solved by dynamic programming.</p> <p>Let's say we have an array of integers:</p> <pre><code>i[1], i[2], i[3], ..., i[n], i[n+1], i[n+2] </code></pre> <p>We partition the array into two parts: the first part containing first n integers, and the second part is the last two integers:</p> <pre><code>{i[1], i[2], i[3], ..., i[n]}, {i[n+1], i[n+2]} </code></pre> <p>Let's denote <code>M_SUM(n)</code> as the max sum of the first n integers per your requirement. </p> <p>There will be two cases:</p> <ol> <li>if <code>i[n]</code> is not counted into <code>M_SUM(n)</code>, then <code>M_SUM(n+2) = M_SUM(n) + MAX(i[n+1], i[n+2])</code></li> <li>if <code>i[n]</code> is counted into <code>M_SUM(n)</code>, then <code>M_SUM(n+2) = M_SUM(n) + i[n+2]</code></li> </ol> <p>then, <code>M_SUM(n+2)</code>, the value we are seeking for, will be the larger value of the above two.</p> <p>Then we can have a very naive pseudocode as below:</p> <pre><code>function M_SUM(n) return MAX(M_SUM(n, true), M_SUM(n, false)) function M_SUM(n, flag) if n == 0 then return 0 else if n == 1 return flag ? i[0] : 0 } else { if flag then return MAX( M_SUM(n-2, true) + i[n-1], M_SUM(n-2, false) + MAX(i[n-1],i[n-2])) else return MAX(M_SUM(n-2, false) + i[n-2], M_SUM(n-2, true)) } </code></pre> <p>"flag" means "allow using the last integer"</p> <p>This algorithm has an exponential time complexity.</p> <p>Dynamical programming techniques can be employed to eliminate the unnecessary recomputation of M_SUM.</p> <p>Storing each <code>M_SUM(n, flag)</code> into a n*2 matrix. In the recursion part, if such a value does not present in the matrix, compute it. Otherwise, just fetch the value from the matrix. This will reduce the time complexity into linear.</p> <p>The algorithm will have O(n) time complexity, and O(n) space complexity.</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