Maximum subarray problem¶
The problem of finding a contiguous interval of a numeric array whose elements have the maximum possible sum.
Core Idea¶
The maximum subarray problem asks for consecutive indices i through j whose array values have the greatest sum. Contiguity is constitutive: an internal negative value can remain when it connects larger positive contributions, while a prefix whose accumulated sum hurts every future extension can be discarded.
Kadane's linear-time recurrence tracks the best sum ending at the current position and the best seen globally. At each element it chooses between starting anew and extending the previous interval. A complete specification must say whether empty output is allowed, how ties are handled, and whether indices or only the sum are returned.
Scope of Application¶
- Algorithm design. Dynamic programming yields a linear scan.
- Time-series analysis. High cumulative-score intervals are identified.
- Image analysis. Higher-dimensional maximum-sum rectangles generalize the problem.
- Teaching. The problem illustrates invariants, divide-and-conquer, and optimization transformations.
Clarity¶
Specify input type, contiguity, empty policy, output indices, tie-breaking, numeric precision, and dimensionality. 'Subsequence' should be avoided unless its contiguity convention is explicit. Inclusion test: A solution is a contiguous interval maximizing the sum under the stated empty/nonempty convention. Exclusion test: The maximum subset sum is excluded because it can skip internal negative entries. Nearest boundary: Maximum subsequence is a common terminological near miss; in algorithms, subsequence often permits noncontiguous selection whereas subarray does not. Exit condition: The identity exits when contiguity, one-dimensional order, additive scoring, or maximization is removed. Common misclassifications: It is not maximum subset sum. It is not necessarily the longest positive run. It is not identical across empty-allowed and nonempty conventions. It is not restricted to Kadane's algorithm, which is one solution method. Nearest named distinctions: Maximum subset sum: Can choose noncontiguous elements. Longest increasing subsequence: Optimizes length under order constraints rather than contiguous sum. Sliding-window maximum: Maximizes individual values or fixed-window aggregates. Maximum subsequence: Often permits gaps unless explicitly defined as contiguous.
Manages Complexity¶
An input of length n contains quadratically many intervals, yet the best-ending invariant reduces search to one pass. That compression depends on additive separability and linear order; multidimensional or constrained variants can be substantially harder.
Abstract Reasoning¶
- Fix empty/nonempty and tie conventions.
- Initialize the best-ending and global-best states consistently.
- For each value, compare starting a new interval with extending the prior best ending here.
- Update start metadata when starting anew.
- Update the global optimum and tie information.
- Return sum and requested indices.
- Validate against all-negative, all-positive, zero, empty, and tied cases.
Knowledge Transfer¶
The recurrence transfers to any ordered additive score where a harmful prefix can be abandoned. It stops at arbitrary subsets, nonadditive interactions, or constraints requiring more state. The cargo is optimal contiguous accumulation through a best-ending invariant.
Neighborhood in Abstraction Space¶
Maximum subarray problem sits in a crowded region of the domain-specific corpus (32nd percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.
Family — Combinatorial Optimization & Game Problems (12 abstractions)
Nearest neighbors
- Partition problem — 0.90
- Matroid-Constrained Number Partitioning — 0.90
- Steiner system — 0.88
- Sexy Primes — 0.88
- Log-Sum Inequality — 0.88
Computed from structural-signature embeddings · 2026-10-08