For example, with the input array $[1,3,-5,7,-12,4,-1,5]$ the output is $8$ because $[4,-1,5] $ produces the largest sum. I think the answer must lie in some kind of back tracking algorithm, but I can't quite it out (meaning I've come nowhere close). I tried taking the maximums of adjacent pairs, but the resulting algorithm does not seem to work. Just brute forcing it is at least $\Omega (n^3) $, and I don't see any obvious improvements from that algorithm.
Any help is appreciated.
Let $a(n)$ denote the sum of the first $n$ elements. You want to maximize $a(i)-a(j)$ where $i> j$. While you are computing these sums, keep track of the smallest one that appears, i.e. let $b(n)=\min\{a(i):i\le n\}$. Then for each $a(n)$ you compute, compute $$d(n)=a(n)-b(n-1)$$ and store the maximum of this value. When you reach the end of the array this value will be your max. That is, if $S$ is the max and the array is of size $m$, $$S=\max\{d(n): 1<n\le m\}$$ Clearly you only loop through the array once and only need to store three variable. I take it the details can be filled in where necessary (I am typing on my phone so I am keeping it short).