For some reason, Leetcode considers this problem easy but I was having a hard time understanding the solutions.
The core concept is pretty straightforward though. As we walk the array, we can either continue with the previous subset that we started, or we can start over with the current element.
Here's the Ruby code for you:
def max_sub_array(arr) pre = cur = arr for i in 1...arr.length # should we continue our streak, or restart here? pre = [pre + arr[i], arr[i]].max # track the highest pre we've seen so far cur = [pre, cur].max # global max of all pre's end return cur # return the global max end puts max_sub_array([-2,1,-3,4,-1,2,1,-5,4])