Walking with a bag of coins that can hold debts: whenever the bag is worth less than nothing, you drop it and start a new bag.
Clues that point here
→ Maximum (or minimum) subarray sum
→ "Contiguous subarray" with the best total
→ Best profit from one buy and one sell
Not this pattern when
✕ Elements can be skipped (that's a subsequence: DP or greedy instead)
✕ The window must have a fixed length (sliding window)
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
Kadane's Algorithm · template
int bestEndingHere = arr[0], best = arr[0];
for (int i = 1; i < arr.length; i++) {
bestEndingHere = Math.max(arr[i], bestEndingHere + arr[i]); // start fresh or extend
best = Math.max(best, bestEndingHere);
}
return best;