Maximum subarray (Kadane) vs divide-and-conquer — proof of correctness?

Q: Maximum subarray (Kadane) vs divide-and-conquer — proof of correctness?

**Target Audience:** Candidates who already know Kadane's algorithm and want to explain why it works and how it compares. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First Two friends want to find the most profitable run of consecutive days in a year of shop takings. The first friend tears the ledger in half and hands one half to each of two helpers: "Find the best run in your half." Each helper tears their half again, and so on, until everyone holds a single day. Then the answers come back up. At each join, the best run is either entirely in the left piece,

The problem

Question presented to candidate: "You know Kadane's algorithm for the maximum subarray sum. Can you prove it is correct? Then describe a divide-and-conquer algorithm for the same problem, prove that one too, and compare them. Sketch both in Python."

What a strong answer should cover:

Kadane's loop invariants (best sum ending at i, best so far) with initialisation, maintenance and termination, and the lemma E(i) = max(a[i], E(i-1) + a[i]) proved by an exchange argument.
Divide and conquer: the left / right / crossing case split, why the crossing sum is best suffix + best prefix, and the strong-induction proof.
Costs: T(n) = 2T(n/2) + O(n) = O(n log n) for the crossing version versus O(n) and O(1) space for Kadane.
The four-value (total, prefix, suffix, best) combine that makes divide and conquer O(n) and becomes a segment tree for range queries.
Python specifics: (lo + hi) // 2 is safe because ints do not overflow, recursion depth is only about log₂ n, and passing bounds instead of slicing avoids copies.

Code / implementation expected: Optional — the proofs matter most; a Python sketch of the crossing-sum recursion and Kadane's loop is a strong finish.

dp
array
Amazon

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Candidates who already know Kadane's algorithm and want to explain why it works and how it compares. Difficulty: Medium Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

Two friends want to find the most profitable run of consecutive days in a year of shop takings.

The first friend tears the ledger in half and hands one half to each of two helpers: "Find the best run in your half." Each helper tears their half again, and so on, until everyone holds a single d

The solution is hidden so you can try first

11 min read · 12 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonCrossing-sum divide and conquer, four-value divide and conquer and Kadane: answers and work counted