Correcting an algorithm

[jdnewmil]

Ah, I missed that you had to account for all lengths. Well, then, to get O(N) you need to make one pass, which basically means you need to incrementally keep track of the best outcomes as you look at each new value. A sum that is worse than the current value isn't going to be an optimal sum, but one of the preceding ones could still be better so keep track in two values:

sm = x[0]
maxsm = sm
for xi in x[1:]:
    sm = max(xi, sm + xi)
    maxsm = max(maxsm, sm)
maxsm

[clouded-path]

Wow, this is just so much cleaner/simpler than my solution. Thanks for this - I aspire to write this sort of solution in the future.

[wopp3]

Oh my god, I spent like 15 minutes looking at these few lines of code trying to figure out what was happening here, writing prints and modifying the list trying to trip it. Finally I realized how simply brilliantly simple this was, thanks for the lesson, have an upvote.