Maximum Sum

You are given a sequence of integers. Your job is to take a continuous chunk of this sequence, such that the sum of its elements is maximized. You only need to return the maximum sum attained.

For example, suppose you are given the sequence (3, -10, 4, -1, 2, 3, 6, -7). You get the maximum sum by taking the elements (4, -1, 2, 3, 6) which sums to 14.

Examples

max_sum((-1, -9, 0, 8, -76, 5, 3)) ➞ 8

max_sum((3, -10, 4, -1, 2, 3, 6, -7)) ➞ 14

max_sum((1, -9, 0, -8, 76, 5, 43)) ➞ 124

Notes

• There are up to 10,000 integers in each sequence.
• It is possible to take a chunk of zero elements. In this case the sum is 0.
• This challenge can be solved in linear time and constant space.