Maximum Subarray Sum and Closest Pair of Points

Posted on | In

Maximum Subarray Sum

Problem Definition

Problem 1. Given a sequence of integers $a_1, \ldots, a_n$, find the maximum sum of a contiguous subsequence. The empty set is also a valid subsequence, with sum 0.

Example: For input 0 100 -50 -60 30 -10 40 5 45 -2 1, the answer is $110 = 30 + (-10) + 40 + 5 + 45$.

$O(n^3)$ Algorithm

1
2
3
4
5
sol ← 0
for each i, j such that 1 ≤ i ≤ j ≤ n do
    if Σ(k=i to j) ak > sol then
        sol ← Σ(k=i to j) ak
return sol

Theorem 1. This algorithm runs in $O(n^3)$ time.

Proof. The number of basic operations performed is proportional to:

\[\sum_{i=1}^{n} \sum_{j=i}^{n} (j - i + 1) = \frac{n(n+1)(n+2)}{6} = O(n^3)\]

$O(n^2)$ Algorithm (Eliminating Redundant Computation)

Key idea: Reuse $a_2+a_3+a_4+a_5$ computed for $i=2, j=5$ when computing $i=2, j=6$.

1
2
3
4
5
6
7
8
sol ← 0
for i ← 1, ..., n do
    sum(i, i-1) ← 0
    for j ← i, ..., n do
        sum(i,j) ← sum(i,j-1) + aj
        if sum(i,j) > sol then
            sol ← sum(i,j)
return sol

Theorem 2. This algorithm runs in $O(n^2)$ time.

Theorem 3 (Correctness). We prove $\text{sum}{i,j} = \sum{k=i}^{j} a_k$ by induction on $j-i$.

  • Base case: If $j - i = 0$, then $\text{sum}{i,i} = \text{sum}{i,i-1} + a_i = \sum_{k=i}^{i} a_k$.
  • Inductive step: For $j - i = d_0 + 1$, $\text{sum}{i,j} = \text{sum}{i,j-1} + a_j = \sum_{k=i}^{j-1} a_k + a_j = \sum_{k=i}^{j} a_k$.

$O(n \log n)$ Algorithm (Divide and Conquer)

Key idea: Like mergesort, split the sequence left and right, then separately compute the maximum subarray that crosses the boundary.

The optimal subsequence must be one of:

  1. Entirely in the left half
  2. Entirely in the right half
  3. Containing both $a_m$ and $a_{m+1}$ at the boundary
1
2
3
4
5
6
7
8
function MaxSumSubseq(s, t):
    if s = t: return max(as, 0)
    m ← ⌊(s+t)/2⌋
    soll ← MaxSumSubseq(s, m)
    solr ← MaxSumSubseq(m+1, t)
    subsoll ← (max subarray sum going left from m)
    subsolr ← (max subarray sum going right from m+1)
    return max(soll, solr, subsoll + subsolr)

Observation 1. For $m > 1$: $\text{subsol}^l_m = \max(\text{subsol}^l_{m-1} + a_m,\ 0)$

Proof. When $\text{subsol}^l_m$ is nonzero, the contiguous subsequence achieving it is the maximum subsequence ending at $a_{m-1}$, extended by $a_m$.

$O(n)$ Algorithm

We ask “where does the optimal subsequence end?” Without computing $\text{subsolr}$, we only track the maximum subarray sum ending at each position $m$.

1
2
3
4
5
6
7
MaxEndingAt1 = max(a1, 0)
for m = 2, ..., n do
    MaxEndingAtm = max(MaxEndingAt(m-1) + am, 0)
sol ← 0
for m = 1, ..., n do
    if MaxEndingAtm > sol then sol ← MaxEndingAtm
return sol

Lower Bound

Theorem 4. There is no deterministic algorithm that solves the maximum subarray problem in sublinear time.

Proof sketch. If such an algorithm existed, for sufficiently large $n_0$ there would be an input where the value at some position $k$ is never read.

  • If every maximum-sum subsequence contains $a_k$: replacing $a_k$ with $-\infty$ yields a wrong answer.
  • Otherwise: replacing $a_k$ with $+\infty$ yields a wrong answer.

Therefore no sublinear algorithm can exist. ∎

Definition of Efficient Algorithm

Definition 1. An algorithm is efficient if its running time is bounded by a polynomial in the input size.

The maximum subarray problem is easy under this criterion. However, some problems are believed to have no efficient algorithms; the theory that studies this is NP-completeness.

Closest Pair of Points

Problem Definition

Problem 2. Given $n$ points $P = \lbrace p_1, \ldots, p_n\rbrace$ in the 2D Euclidean plane, find the closest pair of points.

$(x_i, y_i)$ are the coordinates of $p_i$, and $d(p_i, p_j)$ is the Euclidean distance between two points.

  • Naive algorithm: $O(n^2)$
  • 1D case: $O(n \log n)$ by sorting then scanning
  • Goal: Design an algorithm faster than $O(n^2)$ in 2D

Key Idea

Let $\delta$ be the minimum distance found so far:

  1. Points farther than $\delta$ from the boundary need not be considered.
  2. Only check points inside the center band of width $2\delta$.
  3. If points inside the band are sorted by $y$-coordinate, any pair closer than $\delta$ must be within 11 positions of each other.

Intermediate Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
function ClosestPair(Px):
    if |Px| ≤ 3: enumerate
    Lx ← first ⌊|Px|/2⌋ points,  Rx ← rest
    x* ← max x-coordinate in Lx
    (pl1, pl2) ← ClosestPair(Lx)
    (pr1, pr2) ← ClosestPair(Rx)
    δ ← min{d(pl1,pl2), d(pr1,pr2)}
    S ← points with x-coordinate in (x*-δ, x*+δ)
    Sy ← S sorted by y-coordinate
    for each p ∈ Sy:
        compute distances to next 11 points in Sy, update closest (pm1, pm2)
    return minimum of three results

If $S_y$ is sorted via mergesort in each call:

\[T(n) \leq 2T(n/2) + c_2 n \log n \implies T(n) = O(n \log^2 n)\]

Master Theorem

Theorem 5 (Master Theorem). For constants $a \geq 1$, $b > 1$ and $T(n) = aT(n/b) + f(n)$:

  1. $f(n) = O(n^{(\log_b a) - \epsilon})$ $\implies T(n) = \Theta(n^{\log_b a})$
  2. $f(n) = \Theta(n^{\log_b a} \log^k n)$ $\implies T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$
  3. $f(n) = \Omega(n^{(\log_b a) + \epsilon})$ and $a \cdot f(n/b) \leq cf(n)$ $\implies T(n) = \Theta(f(n))$

Reducing to $O(n \log n)$: Precompute $P_y$ (all points sorted by $y$-coordinate) before recursion and pass it along. In each recursive call, scan $P_y$ to build $S_y$ in $O(n)$.

\[T(n) = 2T(n/2) + \Theta(n) \implies T(n) = O(n \log n)\]

Final Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
sort P by x-coords → Px
let Py = P sorted by y-coords
return ClosestPair(Px, Py)

function ClosestPair(Px, Py):
    if |Px| ≤ 3: enumerate all pairs
    Lx ← first ⌊|Px|/2⌋ points,  Rx ← rest
    Ly, Ry ← lists of Lx, Rx points sorted by y-coordinate
    x* ← max x-coordinate in Lx
    (pl1, pl2) ← ClosestPair(Lx, Ly)
    (pr1, pr2) ← ClosestPair(Rx, Ry)
    δ ← min{d(pl1,pl2), d(pr1,pr2)}
    S ← points with x-coordinate in (x*-δ, x*+δ)
    Sy ← extract points of S by scanning Py (O(n))
    for each p ∈ Sy:
        compute distances to next 11 points in Sy, update closest (pm1, pm2)
    return minimum of three results

Correctness Proof

Lemma 1

If $p_i \in L_x$, $p_j \in R_x$, and $d(p_i, p_j) < \delta$, then $x_i, x_j \in (x^* - \delta,\ x^* + \delta)$.

Proof. Since $x_i \leq x^* \leq x_j$:

\(x^* - x_i \leq x_j - x_i \leq d(p_i, p_j) < \delta\) \(x_j - x^* \leq x_j - x_i \leq d(p_i, p_j) < \delta \qquad \square\)

Lemma 2

If $p, q \in S_y$ and $d(p,q) < \delta$, then $p$ and $q$ are within 11 positions of each other in $S_y$.

Proof. Partition the strip into boxes of side length $\delta/2$. Each row consists of 4 boxes across. Each box contains at most 1 point (two points in the same half cannot be closer than $\delta$). If $p$ and $q$ are 12 or more positions apart, by the pigeonhole principle they cannot both fit within the strip at distance $< \delta$, giving a contradiction. ∎

Theorem 6

The algorithm correctly finds the closest pair of points in $P$.

Proof. By induction on $\lvert P_x\rvert$. The case $\lvert P_x\rvert \leq 3$ is trivial. For $\lvert P_x\rvert \geq 4$, by the inductive hypothesis $(p_{l1}, p_{l2})$ and $(p_{r1}, p_{r2})$ are the closest pairs in each half.

Case 1. $\delta > d(p_{o1}, p_{o2})$: The two closest points must be in different halves. By Lemmas 1 and 2, both are in $S_y$ within 11 positions, so the algorithm finds them.

Case 2. $\delta = d(p_{o1}, p_{o2})$: The minimum of the three results equals $\delta$, the closest pair distance. ∎

Time Complexity

Theorem 7. The algorithm runs in $O(n \log n)$ time.

Proof. Separating $L_y, R_y$ and constructing $S_y$ each take $O(n)$ by scanning $P_y$ once. Therefore $T(n) = 2T(n/2) + \Theta(n)$, which by the Master Theorem gives $T(n) = O(n \log n)$. Preprocessing (sorting) also takes $O(n \log n)$. ∎

Bottom-up approach: Since the structure mirrors mergesort, one can include the $y$-sorted list in the return tuple of each recursive call and build it during the merge step.