Algorithm: Maximum Subarray Sum (Maximum Segment Sum) Problem

Problem Definition#

Given a one-dimensional array $A[1..n]$ containing positive and negative numbers, find a contiguous subarray $A[i..j]$ such that the sum of the elements in the subarray is maximized, i.e., to find:

$\max _{1\leq i\leq j\leq n} \sum_{k=i}^j A[k]$

and return this maximum value. Sometimes, it is also necessary to return the starting and ending positions of this subarray $i, j$ .

Application Scenarios#

Stock Trading Analysis: Find the best times to buy and sell to maximize profit (i.e., the period with the greatest increase).

Financial Data Analysis: Identify the time period with the best company profits.

Image Processing: Find the area with the most concentrated brightness in a pixel array.

DNA Sequence Analysis: Look for the optimal segment in a gene scoring sequence.

Brute Force Solution (Enumeration)#

max_sum = float('-inf')
for i in range(n):
    sum = 0
    for j in range(i, n):
        sum += A[j]
        if sum > max_sum:
            max_sum = sum

There are $O(n^2)$ subarrays. The time complexity is $O(n^2)$ . The sum of the subarray is calculated directly in $O(1)$ during accumulation.

Divide and Conquer Solution#

Idea: Split the array into left and right halves, recursively solve for the maximum subarray in the left half and the right half, and then handle the maximum subarray that crosses the middle. Consider the following three cases:
The maximum subarray is on the left
The maximum subarray is on the right
The maximum subarray crosses the midpoint

Time Complexity
Recurrence relation: $T(n) = 2T(n/2) + O(n)$ , then using the master theorem to obtain
or directly analyzing gives $O(n\log n)$ .

def max_subarray(A, left, right):
    if left == right:
        return A[left], left, right

    mid = (left + right) // 2

    left_sum, l_start, l_end = max_subarray(A, left, mid)
    right_sum, r_start, r_end = max_subarray(A, mid + 1, right)
    cross_sum, c_start, c_end = max_crossing_subarray(A, left, mid, right)

    if left_sum >= right_sum and left_sum >= cross_sum:
        return left_sum, l_start, l_end
    elif right_sum >= left_sum and right_sum >= cross_sum:
        return right_sum, r_start, r_end
    else:
        return cross_sum, c_start, c_end


def max_crossing_subarray(A, left, mid, right):
    sum = 0
    left_max = float('-inf')
    max_left = mid
    for i in range(mid, left - 1, -1):
        sum += A[i]
        if sum > left_max:
            left_max = sum
            max_left = i

    sum = 0
    right_max = float('-inf')
    max_right = mid + 1
    for j in range(mid + 1, right + 1):
        sum += A[j]
        if sum > right_max:
            right_max = sum
            max_right = j

    return left_max + right_max, max_left, max_right

Dynamic Programming Solution#

Idea: Use a variable current_sum to represent the maximum subarray sum ending at the current position. If the current element alone is better, restart the subarray; otherwise, extend the current subarray.

Iteration Equation: $dp[i] = \max\{ dp[i-1] + A[i], A[i]\}$

Time Complexity: $O(n)$

current_sum = max_sum = A[0]
for i in range(1, n):
    current_sum = max(A[i], current_sum + A[i])
    max_sum = max(max_sum, current_sum)

Exercise#

Luogu P1115 Maximum Subarray Sum