Skip to content

Maximum subarray problem

The problem of finding a contiguous interval of a numeric array whose elements have the maximum possible sum.

Version
v1 · 2026-09-28 · History
Domain-specific #
10624
Domain group
Applied Sciences & Engineering
Origin domain
Computer Science & Software Engineering
Subdomains
Algorithm Design, Dynamic Programming → Computer Science & Software Engineering
Aliases
Maximum sum subarray problem, Maximum segment sum problem

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.

Structural Signature

Sig role-phrases:

  • ordered numeric array — provides values and adjacency relation It is essential. Counterfactual: An unordered set has no contiguous intervals.
  • contiguous interval — restricts selection to consecutive indices It is essential. Counterfactual: Choosing arbitrary positive elements solves a different subset problem.
  • additive score — sums all and only values within the interval It is essential. Counterfactual: Another objective defines another segment optimization.
  • global maximum — compares every admissible interval, not merely local extensions It is essential. Counterfactual: A positive local run may be dominated by a longer interval.
  • empty-policy convention — determines the answer on all-negative input It is essential. Counterfactual: Omitting the convention makes results and implementations disagree.
  • best-ending recurrence — tracks maximum sum of an interval ending at each position It is characteristic. Counterfactual: Without this invariant Kadane's update cannot be justified.

What It Is Not

  • 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.
  • Closest near-miss. Maximum subsequence is a common terminological near miss; in algorithms, subsequence often permits noncontiguous selection whereas subarray does not.

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.

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

  1. Fix empty/nonempty and tie conventions.
  2. Initialize the best-ending and global-best states consistently.
  3. For each value, compare starting a new interval with extending the prior best ending here.
  4. Update start metadata when starting anew.
  5. Update the global optimum and tie information.
  6. Return sum and requested indices.
  7. 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.

Examples

Applied / In Practice

For [-2,1,-3,4,-1,2,1,-5,4], the interval [4,-1,2,1] has maximum sum six.

Mapped back: contiguity → The internal -1 is retained because surrounding gains outweigh it..

Applied / In Practice

Under nonempty convention, choose one occurrence of the largest value; under empty-allowed convention, choose sum zero.

Mapped back: convention → Policy changes the valid optimum..

Applied / In Practice

Select every positive entry from separated positions.

Mapped back: boundary → The selection is not contiguous..

Structural Tensions

T1 — Local Loss versus Global Gain. A negative element can belong to the optimum when it bridges larger positive runs.

Diagnostic: Use cumulative contribution rather than filtering signs independently.

T2 — Simple Recurrence versus Output Specification. The best sum is easy to track, but ties, indices, empty intervals, and overflow can change implementation behavior.

Diagnostic: State conventions and retain start/end metadata explicitly.

Structural–Framed Character

Contiguity and sum are structural; empty and tie policies are specification-framed. Algorithm correctness can coexist with user-visible disagreement if conventions are implicit.

Structural Core vs. Domain Accent

The skeleton is maximizing additive weight over intervals in a total order. Algorithms supply recurrence, invariants, complexity, indices, and edge cases. Those commitments define the maximum subarray problem.

  • Approved root. Frozen DAG placement is unparented.

  • Related — Kadane's algorithm, prefix sums, and maximum-sum rectangle. They are a canonical solver, alternate tool, and higher-dimensional extension.

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

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With

  • Maximum subset sum. Tell: Can choose noncontiguous elements.
  • Longest increasing subsequence. Tell: Optimizes length under order constraints rather than contiguous sum.
  • Sliding-window maximum. Tell: Maximizes individual values or fixed-window aggregates.
  • Maximum subsequence. Tell: Often permits gaps unless explicitly defined as contiguous.

References

  • Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Maximum_subarray_problem (revision 1365852288).
  • Preserved source candidate: https://pdfs.semanticscholar.org/bea4/1795adaf240b9db4195b9dc511bd8d46bff1.pdf
  • Preserved source candidate: https://web.archive.org/web/20171026110814/https://pdfs.semanticscholar.org/bea4/1795adaf240b9db4195b9dc511bd8d46bff1.pdf
  • Preserved source candidate: http://ltu.diva-portal.org/smash/get/diva2:995901/FULLTEXT01.pdf
  • Preserved source candidate: https://archive.org/details/programmingpearl00bent
  • Preserved source candidate: https://www.sciencedirect.com/science/article/pii/0167642383900151
  • Preserved source candidate: https://www.aaai.org/Library/ISMB/1999/ismb99-027.php
  • Preserved source candidate: http://dl.acm.org/citation.cfm?id=314613.314823
  • Preserved source candidate: http://www.picb.ac.cn/~xiaohang/vimwiki/study/tanlirong/Algorithm/project/Report.pdf

The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.