🔝53. Maximum Subarray

Medium | Grind 75 | August 26th Friday, 2022

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Constraints:

• 1 <= nums.length <= 105

• -104 <= nums[i] <= 104

Example 1

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Second Tab

Input: nums = [1]
Output: 1

Example 3

Input: nums = [5,4,-1,7,8]
Output: 23

SOLUTION

I struggled to find a solution the first time. This was mainly due to not seeing how negative values affect the sum. When the sum of the contiguous subarray is negative, it is optimal to ditch all the elements you have seen so far and start at the current element as the sum. This is because regardless of the next number, a negative sum plus the current number will always result in lesser sum compared to taking the current element alone.

In terms of coding the solution, we will have a variable max_value that is initially set to negative infinity and will track the maximum sum of the list. We also need a variable (local_max) to keep track of the sum of the current contiguous subarray. We then iterate over all the elements in the list. As we iterate over the list, we will add the element to our local_max and check if the local_max is greater than the max_value. If yes, we update the max_value to the local_max. We then reinitialize the local_max to zero if it is less than 0. We repeat this till the end of the list. In the end, we return the max_value.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # store the maximum sum seen so far - global max
        max_sum = float("-inf")
        
        # current max (may not necessairly be the global max)
        local_max = 0
        
        for num in nums: 
            # add current element to local max
            local_max += num
            
            max_sum = max(max_sum, local_max)
            
            # set local max to 0 if it is negative
            if local_max < 0: 
                local_max = 0
        
        return max_count
    
            
            

TIME AND SPACE COMPLEXITY

TIME: O(n) where n is the length of the list. We iterate over every element in the list once.

SPACE: O(1) we only need two variables regardless of the list size.