Maximum Subarray

Array
Easy

Approach

Diagrams

Analysis

Time

O(n)

Space

O(1)
class Solution:
    def maxSubArray(self, nums):
        maxEndingHere = nums[0]
        maxSoFar = nums[0]

        for idx in range(1, len(nums)):
            num = nums[idx]

            maxEndingHere = max(maxEndingHere + num, num)
            maxSoFar = max(maxSoFar, maxEndingHere)

        return maxSoFar

Learn

#Array

#Kadane's Algorithm

Videos