03
Circular (DP — Kadane / Subarray Sub-pattern)
The best subarray may wrap from the end to the start. A wrapping subarray leaves out a middle piece, so it equals total − (that middle piece); the best wrap removes the minimum subarray.
Signals in the problem statement
- ›
"circular array"
- ›
"the end connects to the start"
- ›
"each element at most once" in a ring
What makes it different
Run max-Kadane and min-Kadane in the same pass. The all-negative case is the trap: there the "wrap" is empty.
Questions
ordered from “learn the idea” to “recognise it without help”- 1Maximum Sum Circular SubarrayWalkthroughMediumBasic Anchor·LeetCode #918
Template
circular-template.cpp
// Circular max subarray: either it doesn't wrap (normal Kadane),
// or it wraps = total minus the minimum middle subarray.
int maxCircular(const vector<int>& a) {
int total = 0, curMax = 0, curMin = 0, bestMax = a[0], bestMin = a[0];
for (int x : a) {
curMax = max(x, curMax + x); bestMax = max(bestMax, curMax);
curMin = min(x, curMin + x); bestMin = min(bestMin, curMin);
total += x;
}
if (bestMax < 0) return bestMax; // all negative: a wrap would be empty
return max(bestMax, total - bestMin);
}Remember this · DP — Kadane / Subarray
Trigger
Maximum (or minimum) sum/product of a contiguous subarray, stock buy/sell, circular arrays.
Think
Is the best subarray ending at i either "i alone" or "best ending at i−1, plus i"?
Key question
Should I extend or restart?