Leetcode 53: Maximum Subarray

The original question can be found here.

The question is aksing for the largest sum of the subarray. We can enumerate all possible subarrays and return the lagest sum. The time complexity is O(n^2)which is not quite acceptable.

To find an optimal solution, we need to use a skill called prefix sum. If you haven’t heard about it before, please refer to my post here.

Let’s take an input example from the question:

nums:                [-2, 1,-3,4,-1,2,1,-5,4]
prefix_sum:        [0,-2,-1,-4,0,-1,1,2,-3,1]

Since we know sum(i...j)= prefix_sum[j + 1] - prefix_sum[i], we need to make prefix_sum[j + 1] as large as possible, and prefix_sum[i] as small as possible. In this problem, we actually don’t have to construct the prefix sum array. We only need to keep track the minimum prefix sum, and update it along the way. Here is the Python code:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        curr_prefix_sum, min_prefix_sum = 0, 0
        res = -math.inf
        for num in nums:
            curr_prefix_sum += num
            res = max(res, curr_prefix_sum - min_prefix_sum)
            min_prefix_sum = min(min_prefix_sum, curr_prefix_sum)
        return res

Note: The final result is initialized as minimum integer, not 0. The reason is we could have an array with only negative integers, so 0 is definitely not the result we want.

Time complexity: O(n). Space complexity: O(1).