53. Maximum Subarray - Explanation

Description

Given an array of integers nums, find the subarray with the largest sum and return the sum.

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

Example 1:

Input: nums = [2,-3,4,-2,2,1,-1,4]

Output: 8

Explanation: The subarray [4,-2,2,1,-1,4] has the largest sum 8.

Example 2:

Input: nums = [-1]

Output: -1

Constraints:

1 <= nums.length <= 1000
-1000 <= nums[i] <= 1000

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.

Hint 1

A brute force approach would be to compute the sum of every subarray and return the maximum among them. This would be an O(n^2) approach. Can you think of a better way? Maybe you should consider a dynamic programming-based approach.

Hint 2

Instead of calculating the sum for every subarray, try maintaining a running sum. Maybe you should consider whether extending the previous sum or starting fresh with the current element gives a better result. Can you think of a way to track this efficiently?

Hint 3

We use a variable curSum to track the sum of the elements. At each index, we have two choices: either add the current element to curSum or start a new subarray by resetting curSum to the current element. Maybe you should track the maximum sum at each step and update the global maximum accordingly.

Hint 4

This algorithm is known as Kadane's algorithm.

Company Tags

1. Brute Force

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n, res = len(nums), nums[0]
        for i in range(n):
            cur = 0
            for j in range(i, n):
                cur += nums[j]
                res = max(res, cur)
        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Recursion

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        def dfs(i, flag):
            if i == len(nums):
                return 0 if flag else -1e6
            if flag:
                return max(0, nums[i] + dfs(i + 1, True))
            return max(dfs(i + 1, False), nums[i] + dfs(i + 1, True))
        return dfs(0, False)

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n)$

3. Dynamic Programming (Top-Down)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        memo = [[None] * 2 for _ in range(len(nums) + 1)]

        def dfs(i, flag):
            if i == len(nums):
                return 0 if flag else -1e6
            if memo[i][flag] is not None:
                return memo[i][flag]
            if flag:
                memo[i][flag] = max(0, nums[i] + dfs(i + 1, True))
            else:
                memo[i][flag] = max(dfs(i + 1, False),
                                    nums[i] + dfs(i + 1, True))
            return memo[i][flag]

        return dfs(0, False)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Dynamic Programming (Bottom-Up)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [[0] * 2 for _ in range(n)]
        dp[n - 1][1] = dp[n - 1][0] = nums[n - 1]
        for i in range(n - 2, -1, -1):
            dp[i][1] = max(nums[i], nums[i] + dp[i + 1][1])
            dp[i][0] = max(dp[i + 1][0], dp[i][1])

        return dp[0][0]

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

5. Dynamic Programming (Space Optimized)

class Solution:
    def maxSubArray(self, nums):
        dp = [*nums]
        for i in range(1, len(nums)):
            dp[i] = max(nums[i], nums[i] + dp[i - 1])
        return max(dp)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

6. Kadane's Algorithm

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxSub, curSum = nums[0], 0
        for num in nums:
            if curSum < 0:
                curSum = 0
            curSum += num
            maxSub = max(maxSub, curSum)
        return maxSub

Time & Space Complexity

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

7. Divide & Conquer

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        def dfs(l, r):
            if l > r:
                return float("-inf")

            m = (l + r) >> 1
            leftSum = rightSum = curSum = 0
            for i in range(m - 1, l - 1, -1):
                curSum += nums[i]
                leftSum = max(leftSum, curSum)

            curSum = 0
            for i in range(m + 1, r + 1):
                curSum += nums[i]
                rightSum = max(rightSum, curSum)

            return (max(dfs(l, m - 1),
                        dfs(m + 1, r),
                        leftSum + nums[m] + rightSum))

        return dfs(0, len(nums) - 1)

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(\log n)$