Leetcode 53 - Maximum Subarray

Table of contents

Problem

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.

Constraints:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

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.

Explanation/Approach

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.

• Kadane’s Algorithm: This dynamic programming approach involves iterating through the array and at each step, deciding whether to add the current element to the existing subarray or start a new subarray.

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.

Explanation

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.