53. Maximum Subarray Medium

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

A subarray is a contiguous non-empty sequence of elements within an array.

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

Example 2:
Input: nums = [1]
Output: 1

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

Approach

Input: An array nums

Output: Find a contiguous subarray with the largest sum and return its maximum sum.

This problem belongs to Dynamic Programming problems.

The most classic solution is Kadane's algorithm: one traversal, maintaining the "maximum subarray sum ending at the current element", and synchronously updating the global maximum value.

State definition:

• curr: the maximum sum ending at the current position (either merge itself into the previous sum, or start fresh from itself).
• best: the global maximum sum.

Key points / Common mistakes:

• When the array is all negative numbers, the answer is "the largest negative number"; initializing to nums[0] naturally covers this case.
• Do not initialize curr to 0 (will incorrectly ignore an all-negative array).

Implementation

python

from typing import List

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # curr: maximum subarray sum ending at the current element
        # best: global maximum subarray sum
        curr = best = nums[0]
        for x in nums[1:]:
            # Either append the current element to the previous max sum, or start fresh from the current element
            curr = max(x, curr + x)
            best = max(best, curr)
        return best

javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let curr = nums[0];
    let best = nums[0];

    for (let i = 1; i < nums.length; i++) {
        curr = Math.max(nums[i], curr + nums[i]);
        best = Math.max(curr, best);
    }

    return best;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Links

53. Maximum Subarray (English)

53. 最大子数组和 (Chinese)