Maximum Subarray (Kadane's Algorithm) & Circular Array Extensions

From 2D Image Estimation to $O(N)$ 1D Dynamic Programming

Originally posed by Ulf Grenander in 1977 for maximum-likelihood pattern detection in 2D digitized images, the Maximum Contiguous Subarray problem originally took $O(N^3)$ brute force, $O(N^2)$ via prefix sums, and $O(N \log N)$ via divide-and-conquer before Jay Kadane (CMU) discovered the $O(N)$ invariant in 1984. Notice the structural connection to prefix sums:

$$\max_{0 \le L \le R < N} \sum_{k=L}^{R} A[k] = \max_{0 \le R < N} \left( P[R+1] - \min_{0 \le L \le R} P[L] \right)$$

Maintaining the running minimum prefix sum $\min_{0 \le L \le R} P[L]$ as $R$ scans left-to-right is mathematically identical to Kadane's DP recurrence: let $E[i]$ be the maximum sum of a non-empty contiguous subarray ending at index $i$. Whenever $E[i-1] < 0$, prepending the best suffix of $A[0 \dots i-1]$ to $A[i]$ strictly reduces $A[i]$'s value, so we discard the negative prefix and start a fresh subarray at $i$:

$$E[i] = \max(A[i],\; E[i-1] + A[i]), \qquad G[i] = \max(G[i-1],\; E[i])$$

Comparative Algorithmic Approaches to Maximum Subarray

Visualizing Circular Subarray Complement Duality

Associative Monoid Promotion for Parallel / Segment-Tree Kadane

Production Implementation: Circular Kadane & Index-Tracking Non-Wrapping Kadane

#include <algorithm>
#include <cstdint>
#include <vector>

struct SubarrayResult {
  std::int64_t max_sum;
  std::size_t best_left;
  std::size_t best_right;
};

// Returns maximum non-empty subarray sum along with exact [best_left, best_right] indices
SubarrayResult kadane_with_indices(const std::vector<int>& nums) noexcept {
  std::int64_t cur_sum = nums[0];
  std::int64_t max_sum = nums[0];
  std::size_t cur_left = 0, best_left = 0, best_right = 0;

  for (std::size_t i = 1; i < nums.size(); ++i) {
    if (cur_sum < 0) {
      cur_sum = nums[i];
      cur_left = i;
    } else {
      cur_sum += nums[i];
    }
    if (cur_sum > max_sum) {
      max_sum = cur_sum;
      best_left = cur_left;
      best_right = i;
    }
  }
  return {max_sum, best_left, best_right};
}

// Single-pass O(N) Time, O(1) Space Maximum Circular Subarray
std::int64_t max_subarray_circular(const std::vector<int>& nums) noexcept {
  std::int64_t total_sum = nums[0];
  std::int64_t cur_max = nums[0], global_max = nums[0];
  std::int64_t cur_min = nums[0], global_min = nums[0];

  for (std::size_t i = 1; i < nums.size(); ++i) {
    const std::int64_t x = nums[i];
    total_sum += x;
    cur_max = std::max(x, cur_max + x);
    global_max = std::max(global_max, cur_max);
    cur_min = std::min(x, cur_min + x);
    global_min = std::min(global_min, cur_min);
  }

  // If all numbers are negative, global_max < 0 and total_sum == global_min.
  // Returning total_sum - global_min would erroneously return 0 (the empty subarray).
  if (global_max < 0) {
    return global_max;
  }
  return std::max(global_max, total_sum - global_min);
}