I’ve got this problem on my last exam, which I struggle to deal with.
Lets say we have array of N integers (it can be float too, but lets 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 sum from this operation will be lowest possible.
For example: Lets 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 cant 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 proof 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 cant neither prove it is valid way to solve it, or find any counterexample. So i write here, maybe someone finds it interesting. Thanks for your attention