StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Suppose you have the following array:</p> <pre><code>1, 1, 2, -50, -3, -4, 6, 7, 8. </code></pre> <p>At each entry, we can either continue with our incrementing progression or reset the value to a lower value.<br> <strong>Here there can be only two good options. Either we would choose the maximum possible value for the current entry or the minimum possible(2). (proof towards the end)</strong></p> <p>Now it is clear that 1st 3 entries in our output shall be 2, 3 and 4 (because all the numbers so far are positive and there is no reason to reset them to 2 (a low value).</p> <p>When a negative entry is encountered, compute the sum:<br> <code>-(50 + 3 + 4) = -57</code>.</p> <p>Next compute the similar sum for succeeding +ve contiguous numbers.<br> <code>(6 + 7 + 8) = 21</code>. </p> <p>Since 57 is greater than 21, it makes sense to reset the 4th entry to 2. </p> <p>Again compute the sum for negative entries:<br> <code>-(3 + 4) = -7</code>.</p> <p>Now 7 is less than 21, hence it makes sense not to reset any further because maximum product shall be obtained if positive values are high.</p> <p>The output array thus shall be: </p> <pre><code>2, 3, 4, 2, 3, 4, 5, 6, 7 </code></pre> <p>To make this algorithm work in linear time, you can pre-compute the array of sums that shall be required in computations.</p> <p><strong>Proof:</strong></p> <p>When a negative number is encountered, then we can either reset the output value to low value (say j) or continue with our increment (say i).</p> <p>Say there are k -ve values and m succeeding positive values.</p> <p>If we reset the value to j, then the value of product for these k -ve values and m +ve values shall be equal to: </p> <pre><code>- ( (j-2+2)*a1 + (j-2+3)*a2 + ... + (j-2+k+1)*ak ) + ( (j-2+k+2)*b1 + (j-2+k+3)*b2 + ... + (j-2+k+m+1)*am ) </code></pre> <p>If we do not reset the value to 2, then the value of product for these k -ve values and m +ve values shall be equal to: </p> <pre><code>- ( (i+2)*a1 + (i+3)*a2 + (i+4)*a3 ... + (i+k+1)*ak ) + ( (i+k+2)*b1 + (i+k+3)*b2 + ... + (i+k+m+1)*am ) </code></pre> <p>Hence the difference between the above two expressions is: </p> <pre><code>(i-j+2)* ( sum of positive values - sum of negative values ) </code></pre> <p><strong>Either this number can be positive or negative. Hence we shall tend to make j either as high as possible (M[i-1]+1) or as low as possible (2).</strong></p> <p><strong>Pre-computing array of sums in O(N) time</strong></p> <p><strong>Edited: As pointed out by Evgeny Kluev</strong></p> <ol> <li>Traverse the array backwards. </li> <li>If a negative element is encountered, ignore it. </li> <li>If a positive number is encountered, make suffix sum equal to that value. </li> <li>Keep adding the value of elements to the sum till it remains positive. </li> <li>Once the sum becomes < 0, note this point. This is the point that separates our decision of resetting to 2 and continuing with increment.</li> <li>Ignore all negative values again till you reach a positive value. </li> <li>Keep repeating till end of array is reached.</li> </ol> <p>Note: While computing the suffix sum, if we encounter a zero value, then there can be multiple such solutions.</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