Kadane's Algorithm is a dynamic programming approach used to find the maximum sum of a contiguous subarray within a one-dimensional array of numbers. It is highly efficient, running in
The fundamental idea behind Kadane's algorithm is to iterate through the array and at each element, decide whether to:
- Extend the current subarray by adding the current element.
- Start a new subarray beginning with the current element.
currentSum = Math.max(num, currentSum + num);
maxSum = Math.max(maxSum, currentSum);| Scenario | How it Works | Example Problem |
|---|---|---|
| Standard Maximum Subarray | Find the maximum sum of a contiguous subarray. | Maximum Subarray |
| Circular Subarray Sum | Handle arrays where the end wraps around to the beginning. | Maximum Sum Circular Subarray |
| Maximum Product Subarray | Similar to sum, but tracks both max and min products to handle negative numbers. | Maximum Product Subarray |
| One Deletion Variant | Find max sum where you can delete at most one element. | Maximum Subarray Sum with One Deletion |
Look for these "triggers" in a question:
✅ 1. Contiguous Subarray
- "Find the maximum/minimum sum of a continuous subarray."
✅ 2. Greedy / DP Choice
- "At each point, should I continue the previous sequence or start fresh?"
✅ 3. Linear Time Requirement
- Problems that need to be solved in
$O(n)$ space or time.
When you see an array and need to find an optimal contiguous segment:
- ❓ Am I looking for a sum or product of a contiguous subarray?
- ❓ Can I make a local decision at each index to optimize the global result?
- ❓ Does a "reset" (starting a new subarray) help when the sum becomes negative?
👉 If YES, use Kadane's Pattern.