Maximum Subarray Sum

Problem

Return the largest possible sum of a non-empty contiguous subarray of arr, using Kadane's algorithm in O(n) time.

At each position either extend the previous best subarray or start fresh with the current element, keeping the running maximum. Return 0 for an empty input.

Hint

current = max(x, current + x) decides whether to extend or restart at x.

Test cases

case 1

in: [[-2,1,-3,4,-1,2,1,-5,4]]

expected: 6

case 2

in: [[1]]

expected: 1

case 3

in: [[]]

expected: 0

case 4

in: [[-3,-1,-2]]

expected: -1

case 5

in: [[5,-1,5]]

expected: 9

Starter codePython

def max_subarray_sum(arr):
    # Your code here
    pass

5 test cases · run your code against them in the editor