In linear time, find the maximum sum of all possible contiguous subarrays

[Exsul1]

It seems easy if you define s[j] = sum(arr[i] for i in range(j)) because if the maximum sum of contiguous subarrays is reached for a the range(a, b) of indices, with a <= b, then this sum is s[b] - s[a] and for all c <= b one has s[b] - s[c] <= s[b] - s[a] which means that s[a] <= s[c], hence s[a] is the minimum value of s for all indices smaller than b. Hence the algorithm

start with mv = 0 and sv = 0 and best = 0
for b in range(n):
    sv += arr[b]
    mv = min(mv, sv)
    best = max(best, sv - mv)
return best

I didn't understand most of the that, but I'm going to work on it till I do!