Maximum Subarray

Implementation

• Remember this when explaining:

• Brute force approach:
  • Time complexity = O($n^2$) given there are two expanding while loops
  • Space complexity = O(1) given there is only one constant array

class Solution:

    def maxSubArray(self, nums: List[int]) -> int:

        max_sum = float("-inf")

        start_position = 0

  

        while start_position < len(nums):

            curr_sum = 0

            end_position = start_position

            while end_position < len(nums):

                curr_sum += nums[end_position]

                max_sum = max(curr_sum, max_sum)

                end_position += 1

            start_position += 1

        return max_sum

• Optimal solution
  • Time complexity = O(n)
  • Space complexity = O(1)

class Solution:

    def maxSubArray(self, nums: List[int]) -> int:

        n, maxSum, currSum = len(nums), nums[0], 0

        for i in range(n):

            currSum = max(0, currSum) + nums[i]

            maxSum = max(currSum, maxSum)

        return maxSum

• Here is the more explainable version of Kadane's algorithm:

class Solution:

    def maxSubArray(self, nums: List[int]) -> int:

        maxSub = nums[0]

        curSum = 0

        for i in nums:

            if curSum < 0:

                curSum = 0

            curSum += i

            maxSub = max(maxSub, curSum)

        return maxSub

• The logic is that whenever there is a negative prefix number, we flip the curSum back to 0 and continue incrementing whatever value we come across in the upcoming numbers to find the max sum of a contiguous subarray within the array.
• Keep in mind that in this approach we completely disregard negative values so if for any reason there was a negative integer array it would mean that the max sum would only ever be 0.