Two-Pointer Method: Maximum Subarray

Two-Pointer Method: Maximum Subarray¶

https://java2blog.com/kadane-algorithm-in-java/

In [1]:

def MaxSubarray(arr):
    maxEndHere = 0
    maxSoFar = 0
    for i in range(len(arr)):
        maxEndHere += arr[i]
        if (maxEndHere < 0):
            maxEndHere = 0
 
        if (maxSoFar < maxEndHere):
            maxSoFar = maxEndHere

    return maxSoFar
 
test_list = [1, 8, -3, -7, 2, 7, -1, 9]
maxSum = MaxSubarray(test_list)
print("Maximum subarray is",maxSum)

Maximum subarray is 17