Suppose a sequence records daily change: gains are positive, losses are negative, and the question asks for the best contiguous interval. Testing every start and finish repeats huge amounts of addition. Kadane’s algorithm asks a smaller question at each position: what is the best sum of a non-empty interval that must end here? That local state either extends the previous interval or restarts at the current value. A second state remembers the best interval seen anywhere. Mathematics matters because optimal substructure, a precise invariant and a careful empty-versus-non-empty convention reduce a quadratic search to one linear pass.
The practical search question is not simply “what is this named method?” but “which mathematical structure makes the method work, what does it guarantee, and what evidence would show that it is a poor choice?” This article keeps those questions together so students can connect mathematics education with computing, engineering, data reasoning and careful everyday decisions without turning one technique into a career promise.
Quick navigation: Why it matters · Mechanism · Worked example · Deeper ideas · Investigations · Limits · Learning route · Parent guidance · FAQs · Sources
Why this mathematics matters
Mathematics is important here because it turns an apparently visual or computational trick into a chain of reasons. The representation tells us what information is kept. The equation or invariant explains each legal step. The complexity analysis describes the work. The boundary conditions say when a conclusion should not be trusted. That combination is a practical form of problem-solving literacy.
A strong learner should be able to move in both directions: from a real task to a mathematical model, and from a formal guarantee back to its real meaning. Naming an algorithm is not enough. The useful achievement is to explain why the next operation is valid, check a small instance independently, and notice which assumptions the implementation has added.
Source: Jon Bentley’s 1984 Communications of the ACM article on algorithm design techniques.
Primary or implementation reference: Maximum-subarray reference with the recurrence, history and variant conventions.
How the mechanism works
For a non-empty answer, initialise end_here and best to the first value. At each later value x, set end_here=max(x,end_here+x). If x is larger, any interval ending here is improved by discarding the earlier prefix and restarting. Then set best=max(best,end_here). To return indices, keep a tentative start when restarting and copy it when best improves. This is a dynamic programme compressed to two scalar sums because the next update needs only the previous end_here value, not the whole table. A deterministic tie rule—earliest start, shortest interval or first maximum—must be stated when equal sums occur.
Let E_j=max over 0≤i≤j of the sum from i through j. Every non-empty interval ending at j either contains only a_j or extends an interval ending at j−1, so E_j=max(a_j,E_{j−1}+a_j). Let B_j=max over 0≤k≤j of E_k; then B_j=max(B_{j−1},E_j). Induction proves these recurrences cover every legal interval. Each item causes constant work, giving O(n) time and O(1) extra sum storage. The empty-allowed variant instead uses max(0,end_here+x) and may return sum zero; mixing that convention with a non-empty specification breaks all-negative cases.
Keep a four-column notebook labelled object, rule, guarantee and caveat. In the first column name the inputs and stored state. In the second write one update precisely. In the third state what remains true after the update. In the fourth record a tie, approximation, domain restriction or hardware assumption. This routine prevents symbols from drifting away from their meaning.
Worked example and core calculations
For [−2,1,−3,4,−1,2,1,−5,4], begin with end_here=best=−2. At 1, restart: end_here=1 and best=1. At −3, extend to −2. At 4, restart at index 3, so end_here=4 and best=4. Then the states are 3 after −1, 5 after 2, 6 after 1, 1 after −5 and 5 after 4. The maximum is 6 from indices 3 through 6: [4,−1,2,1]. Direct addition gives 4−1+2+1=6. For [−7,−2,−5], the non-empty version returns −2, while the empty-allowed version returns 0; neither is universally correct without the problem contract.
How to audit the calculation
- Recompute every intermediate value directly from the definition.
- Keep labels, indices, signs, units and normalisation visible.
- Test a case with a known exact answer.
- State tie rules, random seeds, tolerances and boundary conventions.
- Compare with a slower transparent baseline or trusted implementation.
- Separate agreement of numbers from suitability of the real-world model.
Small examples are not childish; they are diagnostic instruments. A five-line trace can reveal a reversed inequality, a missing scale factor or an inconsistent label convention before a large dataset hides the same error behind plausible output.
Four deeper ideas
A bad prefix should be discarded
If the best interval ending before x has a negative sum, adding it makes an interval starting at x worse, so restarting is justified.
To transfer this idea, ask what would remain true if labels, scale or input order changed. Then identify the step whose justification would fail if the stated assumption were removed. This turns the paragraph into a reusable reasoning pattern rather than a fact to memorise.
Did you know? One recurrence replaces a two-dimensional search
The algorithm does not enumerate every interval; it preserves exactly the boundary information the next decision requires.
To transfer this idea, ask what would remain true if labels, scale or input order changed. Then identify the step whose justification would fail if the stated assumption were removed. This turns the paragraph into a reusable reasoning pattern rather than a fact to memorise.
The invariant separates ending-here from best-anywhere
Confusing these two quantities can return an interval that cannot legally extend to the current position.
To transfer this idea, ask what would remain true if labels, scale or input order changed. Then identify the step whose justification would fail if the stated assumption were removed. This turns the paragraph into a reusable reasoning pattern rather than a fact to memorise.
Tie policy belongs to the answer
Equal maximum sums can correspond to different starts and lengths, so reproducible index output needs a declared rule.
To transfer this idea, ask what would remain true if labels, scale or input order changed. Then identify the step whose justification would fail if the stated assumption were removed. This turns the paragraph into a reusable reasoning pattern rather than a fact to memorise.
Twelve practical investigations
1. Classic mixed sequence
Use [−2,1,−3,4,−1,2,1,−5,4]. Trace end_here and best.
What the mathematics reveals: The best interval is [4,−1,2,1] with sum 6. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Keep indices aligned with updates. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
2. All negative
Use [−7,−2,−5]. Compare two conventions.
What the mathematics reveals: Non-empty and empty-allowed answers differ. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: State the contract before coding. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
3. All positive
Use [2,3,1]. Extend at every step.
What the mathematics reveals: The full array is optimal. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Check both endpoints. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
4. Zero ties
Use [0,0,0]. Apply earliest or shortest policy.
What the mathematics reveals: Equal sums do not imply one interval. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Document comparison operators. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
5. Restart point
Use [5,−9,6]. Watch the tentative start.
What the mathematics reveals: A strongly negative prefix is discarded. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Update start only on restart. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
6. Single item
Use [−4]. Initialise from the first value.
What the mathematics reveals: A non-empty answer exists. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Avoid a zero default. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
7. Overflow
Use values near an integer limit. Compute safe bounds.
What the mathematics reveals: The recurrence can be right while arithmetic wraps. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Use a wider or checked type. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
8. Floating point
Use cancelling decimal values. Compare naive and stable sums.
What the mathematics reveals: Representation can shift close decisions. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Avoid exact-equality assumptions. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
9. Streaming
Feed one value at a time. Report current best.
What the mathematics reveals: Only constant state is needed for the score. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Retain values if reconstruction matters. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
10. Circular variant
Allow wrapping around the end. Compare with total minus minimum subarray.
What the mathematics reveals: Changed geometry needs another argument. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Handle all-negative arrays carefully. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
11. Brute-force oracle
Enumerate all intervals on short arrays. Compare sums and tie choices.
What the mathematics reveals: A slow definition validates the fast state. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Match the same contract. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
12. Property testing
Generate random arrays. Compare against the oracle.
What the mathematics reveals: Invariants can be checked automatically. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Retain failing seeds. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
Limits and misconceptions
The standard algorithm finds one contiguous interval under additive scores. It does not select scattered elements, optimise a ratio, obey a maximum length, or handle arbitrary nonlinear rewards without a new state or method. Streaming use can report the best sum and indices seen so far, but cannot later reproduce the interval values unless data are retained. Integer sums may overflow; floating-point data can make near-ties sensitive to rounding. Missing values need a policy. A maximum historical interval does not establish causation or predict the future. For circular arrays, two-dimensional grids, fixed-length windows or online edits, related but different algorithms are required.
Five misconceptions to challenge
- It keeps every possible starting point: It compresses them into the best sum ending at the current position.
- A negative current sum should always be returned as zero: Only the empty-allowed variant uses that convention.
- The best interval may skip a bad middle value: The subarray must be contiguous.
- The maximum sum identifies a unique interval: Ties can produce several correct intervals.
- Linear time prevents overflow or rounding error: Arithmetic representation remains an independent concern.
Another broad misconception is that advanced mathematics automatically creates intelligence, admission, income or employment. It does not. Deliberate study can strengthen modelling, abstraction, calculation and explanation, while real pathways also depend on interests, communication, domain knowledge, opportunities and circumstances outside one topic.
A learning route for students
Move from a visible trace to a symbolic rule, then to code and critique. For every step below, prepare three pieces of evidence: a correct hand example, a boundary or failure case, and a short explanation using the relevant invariant. Do not advance merely because software returned a number.
Step 1: Define a contiguous subarray
Begin with the smallest non-trivial instance that lets you define a contiguous subarray. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 2: Derive the ending-here recurrence
Begin with the smallest non-trivial instance that lets you derive the ending-here recurrence. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 3: Distinguish local and global state
Begin with the smallest non-trivial instance that lets you distinguish local and global state. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 4: Trace a dynamic programme
Begin with the smallest non-trivial instance that lets you trace a dynamic programme. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 5: Handle all-negative inputs
Begin with the smallest non-trivial instance that lets you handle all-negative inputs. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 6: Track interval indices
Begin with the smallest non-trivial instance that lets you track interval indices. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 7: Declare tie rules
Begin with the smallest non-trivial instance that lets you declare tie rules. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 8: Reason about linear time
Begin with the smallest non-trivial instance that lets you reason about linear time. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 9: Guard numeric range
Begin with the smallest non-trivial instance that lets you guard numeric range. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 10: Validate against enumeration
Begin with the smallest non-trivial instance that lets you validate against enumeration. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
A four-week practice plan
- Week 1 — vocabulary and diagrams: define each object, redraw the mechanism and reproduce the worked example.
- Week 2 — equations and manufactured tests: derive the key relation and test inputs with known answers.
- Week 3 — implementation and evidence: use a trusted library, record parameters and compare with a transparent baseline.
- Week 4 — transfer and critique: apply the method to a new context, report limits and identify when a different method is better.
Guidance for parents and educators
Ask “what stays true?” and “what could make this conclusion fail?” before asking for speed. Invite the student to draw the input and output, estimate the result and locate the first step that disagrees with a reference. These prompts reveal conceptual understanding more clearly than memorised terminology.
Advanced enrichment should sit beside secure school foundations in algebra, functions, geometry, statistics and computational thinking. It need not accelerate a student into a fixed career identity. A healthy goal is curiosity with discipline: the learner becomes comfortable reading unfamiliar notation, checking an example, revising a model and communicating uncertainty.
Evidence prompts for a useful conversation
- Which quantity is observed and which is inferred?
- Which step saves work, and why is it allowed?
- Is the claim exact, approximate, probabilistic or empirical?
- What units and conventions are in use?
- Which input makes the method struggle?
- What simple baseline could check the answer?
- What would count as evidence that the parameters are poor?
Mini-project assessment
A strong mini-project contains the original question, a small reproducible dataset, a hand-worked example, code or a spreadsheet trace, at least one boundary test, a comparison with a baseline, and a paragraph on limits. Assess the reasoning trail as well as the final output. Repairing a model after a surprising result is valuable mathematical progress.
Six evidence checks for a finished project
Check 1: Define a contiguous subarray
Ask the student to demonstrate how to define a contiguous subarray without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 2: Derive the ending-here recurrence
Ask the student to demonstrate how to derive the ending-here recurrence without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 3: Distinguish local and global state
Ask the student to demonstrate how to distinguish local and global state without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 4: Trace a dynamic programme
Ask the student to demonstrate how to trace a dynamic programme without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 5: Handle all-negative inputs
Ask the student to demonstrate how to handle all-negative inputs without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 6: Track interval indices
Ask the student to demonstrate how to track interval indices without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Frequently asked questions
What does Kadane’s algorithm find?
A maximum-sum contiguous subarray under a declared empty or non-empty convention.
What is the runtime?
O(n).
What extra space is needed for the sum?
O(1).
Why can the algorithm restart?
A negative carried prefix can only reduce a future interval sum.
Does it return indices?
It can, with tentative and best start and end indices.
What happens when all values are negative?
The non-empty variant returns the least negative element.
May it choose non-adjacent values?
No; contiguity is essential.
Can several answers be correct?
Yes, when maximum sums tie.
Is it predictive?
No; it summarises the supplied sequence.
What should students know first?
Signed numbers, sums, inequalities, arrays and induction.
Useful next reading and sources
Source: Jon Bentley’s 1984 Communications of the ACM article on algorithm design techniques.
Source: Maximum-subarray reference with the recurrence, history and variant conventions.
Related eduKateSG reading: Knuth optimisation and interval dynamic programming.
Related eduKateSG reading: Welford’s algorithm and running statistics.
Related eduKateSG reading: Sliding-window extrema with monotone deques.
Read sources with a question in mind: which definition, theorem, default or limitation is being supported? An authoritative link is useful evidence, but it does not replace a worked calculation or a clear statement of how the source applies to the example.
A cheerful final thought
Mathematics becomes friendlier when every symbol has a job and every claim has a boundary. Start small, make the state visible, test the awkward case, and celebrate the moment when a pattern becomes explainable. That is the practical benefit of learning mathematics: not certainty about every future, but a growing ability to ask better questions and build trustworthy answers.