Why this matters when you build with AI
Many tools in production split a sequence into groups: batching requests, cutting a log into shifts, grouping messages into chunks for a model context window. The first version of such a function is usually a plain dynamic programming (DP) table with two nested loops over the split point and the group count. That is O(k n^2) work. With n = 200,000 items and k = 1,000 groups, it is far too slow.
An AI assistant asked to make it faster often suggests divide and conquer optimisation. The speed-up is real, but it only holds for certain cost functions. When the cost function does not have the required shape, the code still runs, prints a number, and the number is wrong. In the test in this lesson, a program that splits 6 numbers into 3 groups printed 169 where the true minimum is 115, and it printed no warning.
The habit that catches this is cheap. Write a brute-force checker that tries every split on small random inputs, and check the inequality from this lesson before you trust the fast version. The checker is evidence on the inputs it covers, not a proof for all inputs.
Terms you need first
- Partition into k blocks: cut an array of n items into k non-empty pieces that are consecutive. Each item belongs to exactly one piece.
- Layer t: the table of best answers for splitting the first i items into exactly t blocks, for every i. Layer t is built only from layer t - 1.
- Split point (opt): for an item count i in layer t, the number of items j that lie before the last block. The last block then holds items j + 1 to i.
- Cost function w(j, i): the cost of one block that holds items j + 1 to i. The DP uses only w, so the whole question is about w.
- Quadrangle inequality (QI): for every a ≤ b ≤ c ≤ d, the rule w(a, c) + w(b, d) ≤ w(a, d) + w(b, c) holds. In plain words: take two intervals that overlap, then swap their ends. The two new intervals together cost no more than the two original ones. This is also called the Monge condition.
- Prefix sums: P[0] = 0 and P[i] = a_1 + ... + a_i. A block sum is then P[i] - P[j], which takes O(1) time.
- Monotone: a list that never goes down. Here, opt(i) ≤ opt(i + 1) for every i in a layer.
The problem and a worked example
I wrote this problem for the lesson. A delivery route has n stops, and stop i carries a parcel weight a_i, with every a_i a positive whole number. The drivers split the route into exactly k shifts. Each shift covers consecutive stops. A shift costs the square of its total weight, because heavy shifts are much worse than light ones. Find the smallest total cost.
Limits: 1 ≤ k ≤ n ≤ 2000 and 1 ≤ a_i ≤ 10000. The largest possible total is (2 * 10^7)^2 = 4 * 10^14, which fits in a 64-bit integer.
Take the input 4 2 with weights 4 1 3 2. There are three ways to cut it into 2 shifts. The cuts give these totals.
- Shifts [4] and [1 3 2]: 4^2 + 6^2 = 16 + 36 = 52.
- Shifts [4 1] and [3 2]: 5^2 + 5^2 = 25 + 25 = 50.
- Shifts [4 1 3] and [2]: 8^2 + 2^2 = 64 + 4 = 68.
The minimum is 50. Now the same answer through layers. Here P = 0, 4, 5, 8, 10.
Layer 1 is one block that holds the first i items, so its value is w(0, i) = P[i]^2. That gives 16, 25, 64, 100 for i = 1 to 4.
Layer 2 uses layer 1. For each i, try every j from 1 to i - 1 and add prev[j] + w(j, i).
- i = 2: only j = 1. Value 16 + (5 - 4)^2 = 17.
- i = 3: j = 1 gives 16 + (8 - 4)^2 = 32. j = 2 gives 25 + (8 - 5)^2 = 34. The best is 32, with opt = 1.
- i = 4: j = 1 gives 16 + (10 - 4)^2 = 52. j = 2 gives 25 + (10 - 5)^2 = 50. j = 3 gives 64 + (10 - 8)^2 = 68. The best is 50, with opt = 2.
The answer is layer 2 at i = 4, which is 50. The splits were opt = 1, 1, 2 for i = 2, 3, 4. The list never goes down. That pattern is what the speed-up depends on.
The idea: the best split only moves right
Divide and conquer uses the monotone pattern. Pick the middle item mid of a range of i values. Scan the j values that can be its split, find the best one, call it bestj. Then the items left of mid have their split at most bestj, and the items right of mid have their split at least bestj. So each half searches a smaller range of j values.
Each level of the recursion scans about n split values in total, and there are about log n levels. So one layer costs O(n log n), and k layers cost O(k n log n). For n = 2000 and k = 20 that is roughly 20 * 2000 * 11 = 440,000 steps, against about 40 million for the plain loops.
When the speed-up is allowed: the quadrangle inequality
The monotone pattern is guaranteed when the cost function satisfies the quadrangle inequality. Yao proved in 1980 that this inequality lets a DP of this form run faster, and the result is in his paper "Efficient dynamic programming using quadrangle inequalities", STOC 1980. Read the paper for the full argument. Here is the check for our cost.
Our cost is w(j, i) = (P[i] - P[j])^2, where the a values are not negative, so P never goes down. Take a ≤ b ≤ c ≤ d. Expand both sides.
- w(a, c) + w(b, d) - w(a, d) - w(b, c) = 2 * (P[a] - P[b]) * (P[d] - P[c]).
Check with the numbers above, with a = 0, b = 1, c = 2, d = 4, so P[a] = 0, P[b] = 4, P[c] = 5, P[d] = 10. The left side is 25 + 36 - 100 - 1 = -40, and the right side of the formula is 2 * (0 - 4) * (10 - 5) = -40. The two agree.
Now the sign. P[a] ≤ P[b] because a ≤ b and the a values are not negative. P[d] ≥ P[c] for the same reason. So the product is zero or negative, and the inequality holds. Everything rests on the non-negative values. Give the cost a negative number and the sign can flip. The section on breaking below shows this.
Let me be clear about what is known and what is checked. The algebra above proves the inequality for this cost when every a_i is at least zero. The monotone split points follow from the inequality by a standard exchange argument, and Yao's 1980 paper is the usual reference for it. I also checked the inequality by brute force over every quadruple for 40 random arrays, and checked the monotone split points for 500 random inputs. Those are checks, and they agree with the proof.
Standard technique with C++17
The file below holds everything: the cost, the plain DP, the divide and conquer layer, a brute-force checker over all cuts, a monotone checker and a self-test. The program reads n k and then the n weights, and prints the answer. Run ./dc selftest to run the checks.
The program was compiled with g++ -std=c++17 -O2 -Wall -Wextra on g++ 15.2.0. The checks use a fixed random seed, so the numbers below repeat on your machine.
// Split n positive numbers into exactly k consecutive blocks.
// A block costs (sum of its numbers)^2. Minimise the total cost.
// Layers are solved with divide and conquer over the optimal split point.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
long long g_naive_evals = 0;
long long g_dc_evals = 0;
struct Problem {
int n;
vector<ll> P; // P[0] = 0, P[i] = a_1 + ... + a_i (1-based a)
explicit Problem(const vector<ll> &a) : n((int)a.size()), P(a.size() + 1, 0) {
for (int i = 0; i < n; i++) P[i + 1] = P[i] + a[i];
}
// Cost of the block made of items j+1 .. i (1-based), for 0 <= j < i <= n.
ll cost(int j, int i) const {
ll s = P[i] - P[j];
return s * s;
}
};
// Plain DP, O(k n^2). Used as the reference.
ll naive_solve(const Problem &pr, int k) {
int n = pr.n;
vector<ll> prev(n + 1, INF), cur(n + 1, INF);
for (int i = 1; i <= n; i++) prev[i] = pr.cost(0, i); // layer 1
for (int t = 2; t <= k; t++) {
fill(cur.begin(), cur.end(), INF);
for (int i = t; i <= n; i++)
for (int j = t - 1; j < i; j++) {
g_naive_evals++;
cur[i] = min(cur[i], prev[j] + pr.cost(j, i));
}
swap(prev, cur);
}
return prev[n];
}
// Divide and conquer for one layer: cur[i] = min over j of prev[j] + cost(j, i).
// The answer for mid is searched only in [optlo, opthi].
struct LayerDC {
const Problem ≺
const vector<ll> &prev;
vector<ll> &cur;
void solve(int lo, int hi, int optlo, int opthi) {
if (lo > hi) return;
int mid = (lo + hi) / 2;
ll best = INF;
int bestj = optlo;
int last = min(mid - 1, opthi);
for (int j = optlo; j <= last; j++) {
g_dc_evals++;
ll v = prev[j] + pr.cost(j, mid);
if (v < best) { // strict, so the leftmost best j is kept
best = v;
bestj = j;
}
}
cur[mid] = best;
solve(lo, mid - 1, optlo, bestj);
solve(mid + 1, hi, bestj, opthi);
}
};
// Fast version, O(k n log n).
ll dc_solve(const Problem &pr, int k) {
int n = pr.n;
vector<ll> prev(n + 1, INF), cur(n + 1, INF);
for (int i = 1; i <= n; i++) prev[i] = pr.cost(0, i); // layer 1
for (int t = 2; t <= k; t++) {
fill(cur.begin(), cur.end(), INF);
// Layer t: i runs over t..n, and the split j over t-1..n-1.
LayerDC d{pr, prev, cur};
d.solve(t, n, t - 1, n - 1);
swap(prev, cur);
}
return prev[n];
}
// Brute force over every way to place k-1 cuts between the n items.
ll brute_solve(const Problem &pr, int k) {
int n = pr.n;
ll best = INF;
for (int mask = 0; mask < (1 << (n - 1)); mask++) {
if (__builtin_popcount(mask) != k - 1) continue;
ll total = 0;
int start = 0;
for (int g = 0; g < n - 1; g++)
if (mask >> g & 1) { // cut after item g+1 (1-based)
total += pr.cost(start, g + 1);
start = g + 1;
}
total += pr.cost(start, n);
best = min(best, total);
}
return best;
}
// Layers of the plain DP: layers[t][i] for 1 <= t <= kmax.
vector<vector<ll>> naive_layers(const Problem &pr, int kmax) {
int n = pr.n;
vector<vector<ll>> L(kmax + 1, vector<ll>(n + 1, INF));
for (int i = 1; i <= n; i++) L[1][i] = pr.cost(0, i);
for (int t = 2; t <= kmax; t++)
for (int i = t; i <= n; i++)
for (int j = t - 1; j < i; j++)
L[t][i] = min(L[t][i], L[t - 1][j] + pr.cost(j, i));
return L;
}
// True if, in every layer, the smallest optimal split point is nondecreasing in i.
bool monotone_in_every_layer(const Problem &pr, int k) {
int n = pr.n;
auto L = naive_layers(pr, k);
for (int t = 2; t <= k; t++) {
int prev_opt = -1;
for (int i = t; i <= n; i++) {
int opt = -1;
ll best = INF;
for (int j = t - 1; j < i; j++) {
ll v = L[t - 1][j] + pr.cost(j, i);
if (v < best) {
best = v;
opt = j;
}
}
if (opt < prev_opt) return false;
prev_opt = opt;
}
}
return true;
}
// Checks w(a,c) + w(b,d) <= w(a,d) + w(b,c) for all 0 <= a <= b <= c <= d <= n.
long long qi_violations(const Problem &pr, long long &checked) {
long long bad = 0;
checked = 0;
int n = pr.n;
for (int a = 0; a <= n; a++)
for (int b = a; b <= n; b++)
for (int c = b; c <= n; c++)
for (int d = c; d <= n; d++) {
checked++;
if (pr.cost(a, c) + pr.cost(b, d) > pr.cost(a, d) + pr.cost(b, c)) bad++;
}
return bad;
}
int selftest() {
mt19937 rng(20261108u);
auto rnd = [&](int lo, int hi) { return lo + (int)(rng() % (unsigned)(hi - lo + 1)); };
// 1. The quadrangle inequality, exhaustively on random small inputs.
long long qi_checked = 0, qi_bad = 0;
for (int r = 0; r < 40; r++) {
int n = rnd(1, 22);
vector<ll> a(n);
for (auto &x : a) x = rnd(1, 50);
long long c = 0;
qi_bad += qi_violations(Problem(a), c);
qi_checked += c;
}
printf("quadrangle inequality: %lld quadruples checked, %lld violations\n", qi_checked, qi_bad);
// 2. Brute force against the fast solver and the plain DP.
int agree = 0, total = 0;
for (int r = 0; r < 3000; r++) {
int n = rnd(1, 9);
int k = rnd(1, n);
vector<ll> a(n);
for (auto &x : a) x = rnd(1, 20);
Problem pr(a);
ll b = brute_solve(pr, k), d = dc_solve(pr, k), p = naive_solve(pr, k);
total++;
if (b == d && b == p) agree++;
}
printf("brute force vs divide and conquer vs plain DP: %d of %d agree\n", agree, total);
// 3. Monotone split points, checked with the brute-force layers.
int mono_ok = 0, mono_total = 0;
for (int r = 0; r < 500; r++) {
int n = rnd(2, 60);
int k = rnd(2, min(n, 12));
vector<ll> a(n);
for (auto &x : a) x = rnd(1, 1000);
mono_total++;
if (monotone_in_every_layer(Problem(a), k)) mono_ok++;
}
printf("smallest optimal split nondecreasing in every layer: %d of %d inputs\n", mono_ok, mono_total);
// 4. Work done on one fixed input: plain DP against divide and conquer.
int n = 2000, k = 20;
vector<ll> a(n);
for (auto &x : a) x = rnd(1, 10000);
Problem pr(a);
g_naive_evals = 0;
g_dc_evals = 0;
ll p = naive_solve(pr, k);
ll d = dc_solve(pr, k);
printf("n=%d k=%d: answer %lld (plain %lld), evaluations plain=%lld dc=%lld\n", n, k, d, p, g_naive_evals, g_dc_evals);
return (qi_bad == 0 && agree == total && mono_ok == mono_total && p == d) ? 0 : 1;
}
int main(int argc, char **argv) {
if (argc > 1 && string(argv[1]) == "selftest") return selftest();
int n, k;
if (!(cin >> n >> k)) return 0;
vector<ll> a(n);
for (auto &x : a) cin >> x;
printf("%lld\n", dc_solve(Problem(a), k));
return 0;
}The example from the worked section gives this output.
$ printf "4 2\n4 1 3 2\n" | ./dc
50The self-test printed this on my machine.
$ ./dc selftest
quadrangle inequality: 188360 quadruples checked, 0 violations
brute force vs divide and conquer vs plain DP: 3000 of 3000 agree
smallest optimal split nondecreasing in every layer: 500 of 500 inputs
n=2000 k=20: answer 4789035512355 (plain 4789035512355), evaluations plain=37640140 dc=389534Some details matter in the code.
- Layer 1 is written out directly, because it has exactly one split (j = 0) and there is no layer 0 to loop from. Its unused entries hold the sentinel value, and the sentinel must never enter a scan.
- Layer t searches the items i from t to n, and the split j from t - 1 to n - 1. Every j in that range has a finite value in layer t - 1, because that layer is defined for every item count at least t - 1. Starting j at 0 for layer 2 would read a sentinel.
- The scan uses a strict
<, so among equal values the leftmost j is kept. The monotone checker uses the same rule, so it compares the same split points. last = min(mid - 1, opthi)stops the scan at the right end of the allowed range, so the range is never longer than it must be.
Complexity
The plain DP does about k n^2 / 2 cost evaluations. On the fixed input with n = 2000 and k = 20 the self-test counted 37,640,140 of them.
The divide and conquer version does O(k n log n) evaluations, and the same input needed 389,534. The count is machine independent. Your running time will differ, so measure it on your own machine rather than trusting a number from a lesson.
Memory is O(n) for two layers. The layers are swapped in place after each step.
Breaking the inequality
I wanted to see what happens when the cost breaks the rule. The input below has negative weights, which the problem does not allow. Negative weights make P go down, so the sign of the formula flips.
The same DP code, run on the input 6 3 with weights -3 -9 -6 -6 7 0, gave these answers.
- Brute force over all cuts: 115.
- Divide and conquer: 169.
The inequality fails for 32 quadruples of this input. The divide and conquer step then picks a split that is not best, and a wrong split in one layer changes the input of the next layer, so the error can spread. The brute-force checker is what showed the difference. The code printed a number and raised no error.
The brute-force value 115 comes from brute_solve in the same file. The learner can add a line in main that calls it on the same input to see both numbers.
Common mistakes
-
Trusting the speed-up without checking the cost. The symptom is a wrong answer with no error, as in the 169 versus 115 example above. Check the inequality first, then run the brute-force checker on small random inputs.
-
Starting layer 2 with the sentinel values in place. The sentinel is
LLONG_MAX / 4, which is 2305843009213693951. If that number appears in your output, a split that does not exist was used. Start each layer at i = t and j = t - 1, as the code does. -
Overflow. With a_i up to 10^5 and n up to 2 * 10^5, the total can reach 2 * 10^10, and its square reaches 4 * 10^20. A signed 64-bit integer holds at most about 9.2 * 10^18. In C++ this is undefined behaviour, and in practice the output can be negative or wrong. Compute the largest possible value from the limits before you pick the type.
-
Testing only the sample. The sample in the statement has one small case. Random small inputs, all cut counts k from 1 to n, and ties in the data find most bugs in this technique.
-
Assuming a cost that looks sensible satisfies the inequality. Some do and some do not. Run the quadruple check on the real cost before you rely on the speed-up.
Hands-on exercise
Work on your own machine in an empty folder.
-
Save the file from the section above as
dc.cpp, compile it withg++ -std=c++17 -O2 -Wall -Wextra -o dc dc.cpp, and run./dc selftest. Your numbers for the quadruple count, the agreement counts and the evaluation counts should match the output shown, because the seed is fixed. The running time will differ. -
Change the cost to add a fixed penalty of 100 for each block:
return s * s + 100;. Predict first whether the three checks still pass. The penalty adds the same amount to both sides of the inequality, so it should cancel, and the checks should pass. Run it and see. Then change the penalty to a term that depends on the block length, such ass * s + len * len, where len = i - j. Predict again before you run it, and check whether the inequality still holds for your new cost with the quadruple check. -
Use the program on the input
5 3and the weights4 1 3 2 5. Work out the answer by hand first, with the layer method from the worked section, then run the program to check.
Prompt to use with an AI reviewer. Paste the code you want reviewed.
Review this divide and conquer DP for partitioning an array into k blocks.
Check three things: (1) whether the cost function satisfies the quadrangle inequality
for all inputs the problem allows, and where your argument uses non-negative values;
(2) whether each layer's loop ranges start at the right values, and what happens to
sentinel values; (3) whether the code agrees with a brute-force checker on random
inputs with n up to 9. For each claim, say whether you verified it by reading the code,
by a proof, or by running something. Name any claim you could not check.A good answer separates proof from test. It names the non-negativity assumption, and it says it did not run the code if it did not. A bad answer says "the code is correct" without naming a test.
Checklist
- Write the cost function as w(j, i) and check the quadrangle inequality, by algebra or by a checker over every quadruple.
- Check that every value used in a layer is finite, and that the layer starts at i = t and j = t - 1.
- Compare the fast version against brute force on random inputs with n up to 9, with all k from 1 to n.
- Compute the largest possible value from the limits, and check that the type holds it.
- Test ties and the smallest and largest cases, n = 1 and k = n.
Summary
Divide and conquer optimisation turns a layered DP of O(k n^2) work into O(k n log n) when the best split point never moves left. The quadrangle inequality is the test for that property, and for the square-of-block-sum cost it reduces to a sign check on the prefix sums. The proof needs non-negative values. A brute-force checker on small inputs is the practical guard, and it caught a wrong answer in the test here.
Practice
Problem 1. For the cost w(j, i) = (P[i] - P[j])^2 with all a_i ≥ 0, does the inequality hold for the quadruple a = 1, b = 2, c = 2, d = 3? Give the two sides.
Hint: the two sides are equal when b = c. Look at the formula from the lesson.
Show the answer
Both sides are w(1, 2) + w(2, 3) and w(1, 3) + w(2, 2). Since w(2, 2) = 0, the two sides are w(1, 2) + w(2, 3) and w(1, 3). Expanding, the difference is 2 * (P[1] - P[2]) * (P[3] - P[2]), which is zero or negative because P[1] ≤ P[2] and P[3] ≥ P[2]. So the inequality holds.
Problem 2. Explain in one sentence why the divide and conquer step in layer t must not start its j range at 0.
Hint: think about what the layer t - 1 table holds for small item counts.
Show the answer
Layer t - 1 is only defined for item counts from t - 1 up, so a j below t - 1 reads a sentinel value that does not represent a real split, and that value can win the minimum.
Problem 3. Run the program on the input 3 2 with weights 1 2 3. Find the answer by hand first, then check it with the program.
Hint: list the two possible cuts.
Show the answer
The cut after the first item gives blocks [1] and [2 3], costing 1 + 25 = 26. The cut after the second item gives [1 2] and [3], costing 9 + 9 = 18. The answer is 18. Running printf "3 2\n1 2 3\n" | ./dc prints 18.
Problem 4. A plain DP for k = 500 blocks and n = 100,000 items does about k n^2 / 2 evaluations. Roughly how many does divide and conquer do, using k n log2 n as the estimate? Give the order of magnitude.
Hint: log2 of 100,000 is about 17.
Show the answer
The plain DP needs about 500 * (10^5)^2 / 2 = 2.5 * 10^12 evaluations, which is far too many. Divide and conquer needs about 500 * 10^5 * 17 = 8.5 * 10^8 evaluations. That is a large but feasible count for a compiled program, and the exact time depends on your machine.
Problem 5. Write a short brute-force checker in your own words for the monotone property: given the layers, check that for every t the smallest optimal split point is nondecreasing in i. Say what the checker proves and what it does not prove.
Hint: the lesson's monotone_in_every_layer function does exactly this.
Show the answer
The checker loops over t, then over i, computes the smallest best j by scanning every candidate, and compares it with the previous i. It proves the property for the inputs it runs on, and it shows nothing about inputs it did not run. It is evidence, not a proof.