I didn't understand the other solutions, so I wrote this

  • 0

    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[0]
      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
      return cur # return the global max
    puts max_sub_array([-2,1,-3,4,-1,2,1,-5,4])

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.