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.