in O(n)
say for an array [x1, x2, ..., xn] you need to find the maximum sum
of consecutive elements.
Say you start with an answer zero. You run a loop to add up the numbers.
If the sum gets bigger than your answer update it. But if the sum gets
< 0 then then set the sum = 0. This will work.
Why it works?
Say sum(xi, ..., xa) < 0. If you add upto xb then
sum = sum(xi, ..., xa) + sum(x(a+1), ... xb)
= < 0 + sum(x(a+1), ... xb) < sum(x(a+1), ... xb)
So when sum(xi, ..., xa) < 0 this sequence will be better left of from the
answer. Setting up sum = 0 will do that.
Did I explain it correctly or is it more confusing
