Given a sequence of integers of length n, the objective is to identify a contiguous subarray that yields the maximum possible sum. This is a fundamental problem in computer science, solvable through several distinct algorithmic approaches.

Dynamic Programming

The optimal substructure for this problem can be defined by letting f(i) represent the maximum subarray sum ending at index i. The recurrence relation is given by: f(i) = max(f(i-1) + a[i], a[i]). The final result is the maximum value found in the sequence f(1) to f(n).

This approach can be implemented in O(n) time and O(1) space, as we only need to track the previous sum and the global maximum.

def max_subarray_dp(nums):
    max_so_far = float('-inf')
    current_sum = 0
    for value in nums:
        current_sum = max(value, current_sum + value)
        max_so_far = max(max_so_far, current_sum)
    return max_so_far

Prefix Sum Approach

By computing the prefix sums P[i] = sum(a[0]...a[i-1]), any subarray sum from index i to j can be calculated as P[j+1] - P[i]. To maximize this value for a fixed end position j, we need to subtract the minimum prefix sum encountered before j.

This method operates in O(n) time and O(n) space.

def max_subarray_prefix(nums):
    prefix_sum = 0
    min_prefix = 0
    max_total = float('-inf')
    for value in nums:
        prefix_sum += value
        max_total = max(max_total, prefix_sum - min_prefix)
        min_prefix = min(min_prefix, prefix_sum)
    return max_total

Divide and Conquer

For a range [left, right], the maximum subarray sum must exist in one of three locations: entirely in the left half, entirely in the right half, or crossing the midpoint. By recursively solving for the left and right halves and separately calculating the maximum sum that traversse the midpoint, we obtain the result. This strategy runs in O(n log n) time.

def max_crossing_sum(nums, left, mid, right):
    left_part = float('-inf')
    s = 0
    for i in range(mid, left - 1, -1):
        s += nums[i]
        left_part = max(left_part, s)
    right_part = float('-inf')
    s = 0
    for i in range(mid + 1, right + 1):
        s += nums[i]
        right_part = max(right_part, s)
    return left_part + right_part

def divide_and_conquer(nums, left, right):
    if left == right:
        return nums[left]
    mid = (left + right) // 2
    return max(divide_and_conquer(nums, left, mid), 
               divide_and_conquer(nums, mid + 1, right), 
               max_crossing_sum(nums, left, mid, right))