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.