02
Maximum product (DP — Kadane / Subarray Sub-pattern)
Products instead of sums. A negative factor swaps the roles of the largest and smallest product, so both are carried.
Signals in the problem statement
- ›
"maximum product subarray"
- ›
"longest subarray with positive product"
- ›
negatives and zeros in the array
What makes it different
Two running values (curMax, curMin, or the lengths pos, neg) that swap on a negative and reset on a zero.
Questions
ordered from “learn the idea” to “recognise it without help”- 1Maximum Product SubarrayWalkthroughMediumBasic Anchor·LeetCode #152
- 2Maximum Length of Subarray With Positive ProductWalkthroughMediumSlight Variation·LeetCode #1567
Template
max-product-template.cpp
// Max product subarray: a negative swaps the biggest and smallest product,
// so carry both. A zero resets them (x alone is a candidate).
long long maxProduct(const vector<int>& a) {
long long curMax = a[0], curMin = a[0], best = a[0];
for (size_t i = 1; i < a.size(); i++) {
long long x = a[i];
long long hi = max({x, x * curMax, x * curMin}); // use the OLD pair for both
long long lo = min({x, x * curMax, x * curMin});
curMax = hi; curMin = lo;
best = max(best, curMax);
}
return best;
}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?