Micro-Drill #169 — Kadane's Algorithm

Recursion & DP Target: 10s

At each element: extend current subarray or start fresh. The simplest DP pattern — must be instant.

def maxSubArray(nums):
    cur = res = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        res = max(res, cur)
    return res

Type it from memory. Go.