53. Maximum Subarray

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

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

Sliding Window

Let $S_{ij}$ be the sum of the subarray $A[i, j]$. There is a integral insight in this question: take the array $A = [2, 2, -5, 6, 7]$. Notice that $S_{02} = -1$, and $S_{03} = S_{02} + A[3] = 5 < A[3]$. Since subarrays must be contiguous, any subarray containing $S_{02}$ is less than if we simply excluded it! In other words, if we find a subarray $A[i, j]$ with $S_{ij} < 0$, we should simply exclude it from the sum! Our algorithm thus works as follows:

1. Begin summing up elements from the leftmost element. Keep track of the maximum sum seen.
2. If we encounter an element $j$ such that $S_{ij} < 0$, discard the sum and begin counting from $j + 1$.
3. Once we have reached the end of the array, return the maximum seen sum.

def maxSubArray(self, nums: List[int]) -> int:
    max_sum, agg_sum = nums[0], 0
    for r in range(0, len(nums)):
        if agg_sum < 0:
            agg_sum = 0
        agg_sum += nums[r]
        max_sum = max(max_sum, agg_sum)
    
    return max_sum

Time Complexity

The non-constant time in the algorithm consists of the for loop. Each iteration is constant time (if statement which is a comparison, addition operation, and comparison/assignment operation), and there are $n$ iterations. Thus the algorithm takes $\mathcal{O}(n)$ time.

Space Complexity

We only store constant space variables, so the algorithm takes $\mathcal{O}(1)$ space.