53. Maximum Subarray

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/maximum-subarray
• topics: Array, Dynamic Programming

Description

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

Idea

• Kadane’s Algorithm
• Dynamic Programming
• Divide & Conquer

Code

Kadane’s Algorithm

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        current_sum = 0
        best_sum = float('-inf')
        for a in nums:
            current_sum = max(a, current_sum + a)
            best_sum = max(current_sum, best_sum)
        return best_sum

Dynamic Programming

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

Divide & Conquer

class Solution:
    def maxSubArray(self, nums):
        def maxSubArray(A, L, R):
            if L > R: return -inf
            mid, left_sum, right_sum, cur_sum = (L + R) // 2, 0, 0, 0
            for i in range(mid-1, L-1, -1):
                left_sum = max(left_sum, cur_sum := cur_sum + A[i])
            cur_sum = 0
            for i in range(mid+1, R+1):
                right_sum = max(right_sum, cur_sum := cur_sum + A[i])
            return max(maxSubArray(A, L, mid-1), 
                maxSubArray(A, mid+1, R), 
                left_sum + A[mid] + right_sum)
        return maxSubArray(nums, 0, len(nums)-1)