October Problem Solving
https://leetcode.com/problems/maximum-subarray/
Already solved this couple of times. But still feels a new. Probably my brain :)
Started thinking from scratch and found the original Kadane's algorithm.
Keep running sum timeline and stash the max sum when it is bigger than the current max.
Reset the running sum when the current number itself is bigger than the running sum when add to it. Because when you add it running sum is going to decrease and not increase so we can reset comfortably as we have the last max sum stashed safely.
Running sum - we add to it or reset it
Max sum - update if it is lower than running sum