Light Mode
Alexander Mussell

Alexander Mussell

SRE. Weightlifting. Reading.

© 2021

Kadane's Algorithm

Given an array, the algorithm to find the maximum subarray sum in O(1) space is called Kadane’s Algorithm.

class Solution:
    def maxSubArray(self, nums):
        for i in range(1, len(nums)):
            if nums[i-1] > 0:
                nums[i] += nums[i-1]
        return max(nums)

Replace the value of the index before i with the sum of i -1 plus i and iterate through. Then take the max. Easy.