Offensive Security Researcher & Quantum Cryptography Analyst

Divide-and-Conquer Algorithm: The Maximum-Subarray Problem Solved

Abdul Wahab Junaid
Divide-and-Conquer: The Maximum-Subarray Problem

I first encountered the maximum-subarray problem framed around a stock trading scenario, and I think that framing is what makes it click for me: given a series of daily price changes, I want to find the contiguous stretch of days that gives me the best possible profit if I buy at the start and sell at the end of that stretch. It sounds like a small, specific puzzle, but it turns out to be a wonderful vehicle for teaching the divide-and-conquer paradigm, because the “combine” step requires a genuinely clever insight rather than a purely mechanical merge.

History and Background

The maximum-subarray problem, particularly the linear-time solution known as Kadane’s algorithm, is generally credited to Jay Kadane, who came up with the idea in 1984 in response to a talk by Ulf Grenander on a related problem in pattern analysis. The divide-and-conquer version of the solution, which I focus on in this file, is presented in Cormen, Leiserson, Rivest, and Stein’s Introduction to Algorithms as a pedagogical example — not because it’s the fastest known way to solve the problem, but because it’s an excellent showcase for how the divide-and-conquer paradigm handles cases where the “combine” step needs real cleverness, since the best subarray might cross the midpoint of the array rather than living entirely in one half.

Problem Statement

Given an array of numbers (which can include negative numbers), I want to find the contiguous subarray with the largest possible sum. Formally, given $A[1..n]$, I want indices $i$ and $j$ (with $i \leq j$) that maximize:

$$ \sum_{k=i}^{j} A[k] $$

Core Concepts

How It Works

  1. If the array has only one element, that element itself is the maximum subarray (base case).
  2. Otherwise, I find the midpoint and split the array into a left half and a right half.
  3. I recursively find the maximum subarray entirely within the left half.
  4. I recursively find the maximum subarray entirely within the right half.
  5. I find the maximum subarray that crosses the midpoint, by scanning leftward from the midpoint to find the best prefix sum, and scanning rightward from the midpoint to find the best suffix sum, then adding them.
  6. I return whichever of the three candidates (left, right, or crossing) has the largest sum.

Working Principle

The key mechanism that makes this work is the observation that any subarray of the full array falls into exactly one of three categories relative to the midpoint: it lies entirely in the left half, entirely in the right half, or it crosses the midpoint. The first two cases are handled naturally by recursion. The third case can’t be handled recursively because it isn’t a subproblem of either half individually — instead, I compute it directly using a linear scan outward from the midpoint in both directions, since any crossing subarray must include the midpoint element (or the elements immediately adjacent to it), so its maximum value is found by greedily extending outward as far as it remains profitable.

Mathematical Foundation

For the crossing case, I define:

$$ \text{LeftSum} = \max_{i \leq mid} \sum_{k=i}^{mid} A[k], \qquad \text{RightSum} = \max_{j > mid} \sum_{k=mid+1}^{j} A[k] $$

The maximum crossing subarray sum is:

$$ \text{CrossSum} = \text{LeftSum} + \text{RightSum} $$

The overall maximum subarray sum is:

$$ \text{MaxSubarray}(A, low, high) = \max\big(\text{MaxSubarray}(A, low, mid),\ \text{MaxSubarray}(A, mid+1, high),\ \text{CrossSum}\big) $$

The recurrence describing the running time is:

$$ T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n) $$

This is because the two recursive calls each handle half the array, and the crossing-subarray computation takes $\Theta(n)$ time (a linear scan in each direction from the midpoint). Applying the Master Method with $a=2$, $b=2$, $f(n) = \Theta(n)$: since $n^{\log_2 2} = n^1$ matches $f(n) = n$, this is Case 2, giving:

$$ T(n) = \Theta(n \log n) $$

Diagrams

flowchart TD
    A["Array A[low..high]"] --> B{"low == high?"}
    B -- Yes --> C["Return single element as max subarray"]
    B -- No --> D["mid = (low+high)/2"]
    D --> E["Recursively find max subarray in A[low..mid]"]
    D --> F["Recursively find max subarray in A[mid+1..high]"]
    D --> G["Find max crossing subarray through mid"]
    E --> H["Return best of the three candidates"]
    F --> H
    G --> H

Pseudocode

FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high):
    leftSum = -infinity
    sum = 0
    for i = mid downto low:
        sum = sum + A[i]
        if sum > leftSum:
            leftSum = sum
            maxLeft = i

    rightSum = -infinity
    sum = 0
    for j = mid+1 to high:
        sum = sum + A[j]
        if sum > rightSum:
            rightSum = sum
            maxRight = j

    return (maxLeft, maxRight, leftSum + rightSum)

FIND-MAXIMUM-SUBARRAY(A, low, high):
    if high == low:
        return (low, high, A[low])          // base case: single element

    mid = floor((low + high) / 2)

    (leftLow, leftHigh, leftSum) = FIND-MAXIMUM-SUBARRAY(A, low, mid)
    (rightLow, rightHigh, rightSum) = FIND-MAXIMUM-SUBARRAY(A, mid+1, high)
    (crossLow, crossHigh, crossSum) = FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)

    if leftSum >= rightSum and leftSum >= crossSum:
        return (leftLow, leftHigh, leftSum)
    elif rightSum >= leftSum and rightSum >= crossSum:
        return (rightLow, rightHigh, rightSum)
    else:
        return (crossLow, crossHigh, crossSum)

Step-by-Step Example

Let me trace through the array A = [-2, 1, -3, 4, -1, 2, 1, -5, 4] (indices 0 to 8).

I can verify this is indeed the best: no other contiguous run in this array sums higher than 6 — for example, [4] alone gives 4, [-2,1,-3,4,-1,2,1] gives 2, and [4,-1,2,1,-5,4] gives 5, all less than 6.

Time Complexity

Space Complexity

The recursive calls create a call stack of depth $O(\log n)$, and since each call only needs a constant amount of extra space beyond its recursive calls (aside from the input array itself), the auxiliary space complexity is $O(\log n)$.

Correctness Analysis

Correctness follows from the exhaustive case analysis: since every subarray of $A[low..high]$ is either entirely within the left half, entirely within the right half, or crosses the midpoint, and the algorithm correctly computes the best subarray for each of these three cases, taking the maximum of the three guarantees I’ve found the true overall maximum. The crossing case is proven correct because any subarray crossing the midpoint can be decomposed uniquely into a suffix of the left half plus a prefix of the right half, and maximizing each side independently (both anchored at the midpoint) and adding them together does correctly maximize their sum, since the two parts don’t interact with each other once fixed at the midpoint boundary.

Advantages

Disadvantages

Applications

Implementation in C

#include <stdio.h>
#include <limits.h>

/* Finds the maximum crossing subarray sum through the midpoint.
   Updates crossLow and crossHigh to the boundary indices found. */
int maxCrossingSubarray(int A[], int low, int mid, int high, int *crossLow, int *crossHigh) {
    int leftSum = INT_MIN, sum = 0;
    int maxLeft = mid;
    for (int i = mid; i >= low; i--) {
        sum += A[i];
        if (sum > leftSum) {
            leftSum = sum;
            maxLeft = i;
        }
    }

    int rightSum = INT_MIN;
    sum = 0;
    int maxRight = mid + 1;
    for (int j = mid + 1; j <= high; j++) {
        sum += A[j];
        if (sum > rightSum) {
            rightSum = sum;
            maxRight = j;
        }
    }

    *crossLow = maxLeft;
    *crossHigh = maxRight;
    return leftSum + rightSum;
}

/* Recursively finds the maximum subarray sum in A[low..high].
   Stores the resulting boundary indices in *resultLow and *resultHigh. */
int maxSubarray(int A[], int low, int high, int *resultLow, int *resultHigh) {
    if (low == high) {
        *resultLow = low;
        *resultHigh = high;
        return A[low];
    }

    int mid = (low + high) / 2;

    int leftLow, leftHigh, rightLow, rightHigh, crossLow, crossHigh;
    int leftSum = maxSubarray(A, low, mid, &leftLow, &leftHigh);
    int rightSum = maxSubarray(A, mid + 1, high, &rightLow, &rightHigh);
    int crossSum = maxCrossingSubarray(A, low, mid, high, &crossLow, &crossHigh);

    if (leftSum >= rightSum && leftSum >= crossSum) {
        *resultLow = leftLow;
        *resultHigh = leftHigh;
        return leftSum;
    } else if (rightSum >= leftSum && rightSum >= crossSum) {
        *resultLow = rightLow;
        *resultHigh = rightHigh;
        return rightSum;
    } else {
        *resultLow = crossLow;
        *resultHigh = crossHigh;
        return crossSum;
    }
}

int main() {
    int A[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(A) / sizeof(A[0]);

    int resultLow, resultHigh;
    int maxSum = maxSubarray(A, 0, n - 1, &resultLow, &resultHigh);

    printf("Maximum subarray sum: %d\n", maxSum);
    printf("Subarray indices: [%d, %d]\n", resultLow, resultHigh);
    printf("Subarray: ");
    for (int i = resultLow; i <= resultHigh; i++)
        printf("%d ", A[i]);
    printf("\n");

    return 0;
}

Sample Input and Output

For the array [-2, 1, -3, 4, -1, 2, 1, -5, 4], the program outputs:

Maximum subarray sum: 6
Subarray indices: [3, 6]
Subarray: 4 -1 2 1

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version