I've got this problem on my last exam, which I struggle to deal with.

Let's say we have array of $N$ integers (it can be float too, but let's say integers for sake of simplicity. We need to sum those numbers, but we can only use operation of summing two adjacent numbers. Goal of algorithm is to sum this sequence, so maximum of absolute values fromm sum from this operation will be lowest possible.

For example: Let's say we have array -2 5 -3. First we sum 5 and -3, so the temporary sum is 2, and our sequence changes to -2 2. Then we sum -2 and 2, so now our temporary sum is 0. As we see, maximum of temporary sums was 2, and we can't get any lower. (summing -2 and 5 would give us 3, which is higher that 2).

My goal on that exam was to find best complexity algorithm, and prove its correctness.

What I tried:
First thought was to use greedy algorithm, so just sum those two numbers which give lowest temporary sum right now.
Problem is, I can neither prove it is valid way to solve it, nor find any counterexample.

  • $\begingroup$ cs.stackexchange.com/q/59964/755 $\endgroup$ – D.W. Aug 15 at 7:29
  • $\begingroup$ It isn't clear whether you are trying to minimize the sum of two adjacent numbers in a single iteration (trivial) or throughout all the algorithm runtime. $\endgroup$ – Acsor Aug 15 at 11:42
  • $\begingroup$ throughout all the algorithm runtime, sorry, forgot to mention $\endgroup$ – yossi Aug 15 at 11:51
  • $\begingroup$ Just to confirm. The example in the block quote is part of the statement and not your own interpretation of the problem, right? So, it is part of the problem that they don't count the maximum absolute value of the elements in the input, right? $\endgroup$ – plop Aug 15 at 16:23
  • $\begingroup$ Greedy algorithm does not work. $\endgroup$ – John L. Aug 15 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.