LeetCode 53. Maximum Subarray

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example:

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

Solution Explanation

1. For a given array. Eg. [-2, 1, -3, 4, -1, 2, 1, -5, 4]
2. Iterate from index 0 to the last index.
3. At each iteration keep track of the sum up to that index (say currentSum) and check whether the maximum sum needs to be updated. BUT HOW REALLY?
4. Well, the idea is: at given index, if the total sum (currentSum) up to previous index was negative then, disregard the sum. We don’t need to consider the negative value sum because (think about it) adding it to the current sum will only decrease the sum. So if the sum was negative then we reset it to 0.
5. Otherwise, if the sum is positive we don’t need to do anything, but move on the next step.
6. Then add the the current number to the sum.
7. And finally check and update the maximum sum

The following table shows what happens at each iteration for input array of [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

Pseudo Code

Algorithm maxSubArray(nums):
    
    currentSum = 0
    maxSum = nums[0]
    
    for n in nums do:
        
        if currentSum < 0 then:
            currentSum = 0      // reset the current track of sum only if previous currentSum was negative
        end if
        
        currentSum += n         // add the number to current sum
        maxSum = max(currentSum, maxSum)
        
    end for
    
    return maxSum

Python Implementation

def maxSubArray(nums):
    
    sum = 0
    maxSum = nums[0]
    
    for n in nums:
        if sum < 0:
            sum = 0
        
        sum += n
        maxSum = max(sum, maxSum)
        
    return maxSum

nums = [-2,1,-3,4,-1,2,1,-5,4]
# Output: 6
print(maxSubArray(nums))


nums = [1]
# Output: 1
print(maxSubArray(nums))


nums = [5,4,-1,7,8]
# Output: 23
print(maxSubArray(nums))