StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I'd like to combine Amnon's observation about multiplying powers of 2 with one of mine concerning sublists.</p> <p>Lists are terminated hard by 0's. We can break the problem down into finding the biggest product in each sub-list, and then the maximum of that. (Others have mentioned this).</p> <p>This is my 3rd revision of this writeup. But 3's the charm...</p> <p><strong>Approach</strong></p> <p>Given a list of non-0 numbers, (this is what took a lot of thinking) there are 3 sub-cases:</p> <ol> <li>The list contains an even number of negative numbers (possibly 0). This is the trivial case, the optimum result is the product of all numbers, guaranteed to be positive.</li> <li><p>The list contains an odd number of negative numbers, so the product of all numbers would be negative. To change the sign, it becomes necessary to sacrifice a subsequence containing a negative number. Two sub-cases:</p> <p>a. sacrifice numbers from the left up to and including the leftmost negative; or</p> <p>b. sacrifice numbers from the right up to and including the rightmost negative.</p> <p>In either case, return the product of the remaining numbers. Having sacrificed exactly one negative number, the result is certain to be positive. Pick the winner of (a) and (b).</p></li> </ol> <p><strong>Implementation</strong></p> <p>The input needs to be split into subsequences delimited by 0. The list can be processed in place if a driver method is built to loop through it and pick out the beginnings and ends of non-0 sequences.</p> <p>Doing the math in longs would only double the possible range. Converting to log2 makes arithmetic with large products easier. It prevents program failure on large sequences of large numbers. It would alternatively be possible to do all math in Bignums, but that would probably perform poorly. </p> <p>Finally, the end result, still a log2 number, needs to be converted into printable form. Bignum comes in handy there. There's <code>new BigInteger("2").pow(log);</code> which will raise 2 to the power of <code>log</code>.</p> <p><strong>Complexity</strong></p> <p>This algorithm works sequentially through the sub-lists, only processing each one once. Within each sub-list, there's the annoying work of converting the input to log2 and the result back, but the effort is linear in the size of the list. In the worst case, the sum of much of the list is computed twice, but that's also linear 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