LeetCode: 53. Maximum Subarray

53. Maximum Subarray

53. Maximum Subarray

Summary

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

Example:

• Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
• Output: 6

Approach

Use prefix sums.

You can calculate the largest subarray sum with:

largest sum = current prefix sum - minimum prefix sum

This is not a sliding window problem. The array can contain positive, negative, and zero values, so the window does not change monotonically. Because of that, a sliding window approach does not work here.

Function

Initialization:

• prefix = 0
• min_prefix = 0
• best = nums[0]

Do not initialize best to 0 because the array can contain only negative values. For example, if the array is [-1, -2], the maximum sum should be -1.

For each number n in nums:

• prefix += n
• best = max(best, prefix - min_prefix)
• min_prefix = min(min_prefix, prefix)

Return best.

Complexity

Time complexity: O(N) Space complexity: O(1)