can someone explain this algorithm to me?

[SelArom]

the code is attached. I've gone over it a few times, but I can't figure out exactly what it is doing. The way I solved it was to iterate over the list n times, each time summing that element, then that and the next, then the next and so on until you find the occurence with the largest sum...

but this one does it by just passing over the array once, how does that work? I know the meat is in the for-loop but I don't see how this works to find the largest sum! how does this work?

thanks!
-SelArom

 

[CTho9305]

That's clever, and after I thought about it for a bit, it makes sense.

Consider [1, 2, 3, -4, 1]. When it reaches the -4, "best" will be 6. It will update current to 3, and then to 4. It will have properly found the best overall pattern.

Consider [1, -4, 2, 3]. When it reaches the -4, current will be reset. You only reset the current sum when it's negative, because even if you just hit a negative number, the overall contribution of the running subarray is still positive. Keep in mind that you don't care where the start of the subsequence is - only what its sum is.

I'm having a hard time explaining it, but it does make sense once you get it 🙂.