StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>EDIT: I adjusted the algorithm outline to match the actual pseudo code and put the complexity analysis directly into the answer:</p> <p><strong>Outline of algorithm</strong></p> <p>Go seqentially over the sequence and store value and first/last index of the product (positive) since the last 0. Do the same for another product (negative) which only consists of the numbers since the first sign change of the sequence. If you hit a negative sequence element swap the two products (positive and negative) along with the associagted starting indices. Whenever the positive product hits a new maximum store it and the associated start and end indices. After going over the whole sequence the result is stored in the maximum variables.</p> <p>To avoid overflow calculate in binary logarithms and an additional sign.</p> <p><strong>Pseudo code</strong></p> <pre><code>maxProduct = 0 maxProductStartIndex = -1 maxProductEndIndex = -1 sequence.push_front( 0 ) // reuses variable intitialization of the case n == 0 for every index of sequence n = sequence[index] if n == 0 posProduct = 0 negProduct = 0 posProductStartIndex = index+1 negProductStartIndex = -1 else if n < 0 swap( posProduct, negProduct ) swap( posProductStartIndex, negProductStartIndex ) if -1 == posProductStartIndex // start second sequence on sign change posProductStartIndex = index end if n = -n; end if logN = log2(n) // as indicated all arithmetic is done on the logarithms posProduct += logN if -1 < negProductStartIndex // start the second product as soon as the sign changes first negProduct += logN end if if maxProduct < posProduct // update current best solution maxProduct = posProduct maxProductStartIndex = posProductStartIndex maxProductEndIndex = index end if end if end for // output solution print "The maximum product is " 2^maxProduct "." print "It is reached by multiplying the numbers from sequence index " print maxProductStartIndex " to sequence index " maxProductEndIndex </code></pre> <p><strong>Complexity</strong></p> <p>The algorithm uses a single loop over the sequence so its O(n) times the complexity of the loop body. The most complicated operation of the body is log2. Ergo its O(n) times the complexity of log2. The log2 of a number of bounded size is O(1) so the resulting complexity is O(n) aka linear.</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