max-subarray

Maximum Subarray Problem

53. Maximum Subarray

Approach 1: Optimized Brute Force

Brute force, but we don’t have to reconstruct the subarray each time.

max_sum = -math.inf
for i in range(len(nums)):
    cur_sum = 0
    for j in range(i, len(nums)):
        cur_sum += nums[j]  # update the current subarray sum
        max_sum = max(max_sum, cur_sum)
return max_sum

Approach 2: DP, Kadane’s Algorithm

See the linked note.

Approach 3: Divide and Conquer

Not as fast but an interesting alternative.

• Best combined sum
  • The best sum from left (must adjacent to mid)
  • The best sum from right (must adjacent to mid)
• Left half with recursion
• Right half with recursion

def helper(left, right):
    nonlocal nums
    if left > right:
        return -math.inf
 
    mid = (left + right) // 2
    curr = best_left_sum = best_right_sum = 0
 
    for i in range(mid - 1, left - 1, -1):
        curr += nums[i]
        best_left_sum = max(best_left_sum, curr)
 
    curr = 0
    for i in range(mid + 1, right + 1):
        curr += nums[i]
        best_right_sum = max(best_right_sum, curr)
 
    best_combined_sum = nums[mid] + best_left_sum + best_right_sum
 
    left_half = helper(left, mid - 1)
    right_half = helper(mid + 1, right)
 
    return max(best_combined_sum, left_half, right_half)
 
return helper(0, len(nums) - 1)