Skip to content

Leetcode 53 - Maximum Subarray

Difficulty: medium

Table of contents

Open Table of contents


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

Example 1:

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.

Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.


Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.


This problem is a classic example of dynamic programming and can also be solved using divide and conquer. The key idea is to find the maximum sum of a contiguous subarray within a given one-dimensional array.

Solution 1: Kadane’s Algorithm

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = current_sum = nums[0]

        for num in nums[1:]:
            current_sum = max(num, current_sum + num)
            max_sum = max(max_sum, current_sum)

        return max_sum

Time and Memory Complexity

The time complexity is O(n) as it requires a single pass through the array. The space complexity is O(1) as it only uses a few variables.


Kadane’s algorithm iterates through the array, updating the current subarray sum. If adding the current element results in a larger sum than the element itself, it is added to the current sum. Otherwise, the current sum is reset to the current element. The maximum sum is updated at each step.