Take the locally best choice and prove it never hurts.
Reach for it when
Jump / reach problems, gas stations
Choosing a running best (maximum subarray)
An exchange argument shows the local choice is safe
Core idea
A greedy algorithm commits to one choice per step without backtracking. It is correct only when you can argue that any optimal solution can be transformed to include the greedy choice. Kadane's algorithm is the classic: a negative running sum can never help a later subarray, so drop it.
Template · Usually O(n) or O(n log n) with sorting
defmax_subarray(nums):
best = cur = nums[0]
for x in nums[1:]:
cur =max(x, cur + x) # restart if the prefix hurts
best =max(best, cur)
return best
intmaxSubarray(constvector<int>&nums) {
int best = nums[0], cur = nums[0];
for (int i =1; i < (int)nums.size(); i++) {
cur =max(nums[i], cur + nums[i]); // restart if the prefix hurts
best =max(best, cur);
}
return best;
}
Common pitfalls
Greedy without a proof: test against brute force on small inputs