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

[deanhystad]

Generate random lists of numbers and use the posted code(s) to compute the answer. You don't need an answer sheet when you have code that generates the correct answer.

Personally I think a lot of insight is gained by solving this problem by hand. I blanked on this problem until I wrote a list of numbers and a list of sums. I looked at that for about 10 seconds and the solution was immediately obvious.