Kadane’s Algorithm is one of those problems that looks simple on the surface but teaches a very important mindset in problem solving.
It helps you find the maximum sum of a contiguous subarray in an array in O(n) time.
If you try to solve this naively, you might think of checking all subarrays, which takes O(n²) or even O(n³).
Kadane reduces this to a single pass.
Let’s understand it like an engineer, not just memorizing code.
Problem Statement
Given an integer array nums, find the contiguous subarray with the largest sum and return that sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
The subarray [4,-1,2,1] gives sum = 6.
Mental Model
Think of walking through the array and carrying a "running sum".
At every element, you ask yourself:
"Should I continue my current subarray, or start fresh from here?"
That’s the entire idea.
If your current sum becomes negative, it will only hurt future sums.
So you drop it.
This is the key intuition.
Core Idea
At each index i, you decide:
currentSum = max(nums[i], currentSum + nums[i])
Meaning:
Either start a new subarray from nums[i]
Or extend the previous subarray
And track the best answer:
maxSum = max(maxSum, currentSum)
Step by Step Intuition
Let’s take this array:
[-2,1,-3,4,-1,2,1,-5,4]
We move left to right.
Start:
currentSum = -2
maxSum = -2
Now process each element:
Index 1 → 1
currentSum = max(1, -2 + 1) = 1
maxSum = max(-2, 1) = 1
Index 2 → -3
currentSum = max(-3, 1 - 3) = -2
maxSum = 1
Index 3 → 4
currentSum = max(4, -2 + 4) = 4
maxSum = 4
Notice here, we dropped previous sum and started fresh.
Index 4 → -1
currentSum = max(-1, 4 - 1) = 3
maxSum = 4
Index 5 → 2
currentSum = 5
maxSum = 5
Index 6 → 1
currentSum = 6
maxSum = 6
Index 7 → -5
currentSum = 1
maxSum = 6
Index 8 → 4
currentSum = 5
maxSum = 6
Final answer = 6
Why It Works
The key observation is this:
A negative sum will always reduce your future total.
So instead of carrying baggage, you reset.
This is similar to dropping a bad investment early instead of trying to recover it.
Kadane is greedy but correct because at every step, it makes the best local decision that leads to global optimum.
C++ Implementation
class Solution { public: int maxSubArray(vector<int>& nums) { int currentSum = nums[0]; int maxSum = nums[0]; for(int i = 1; i < nums.size(); i++){ // Either extend or restart currentSum = max(nums[i], currentSum + nums[i]); // Update global max maxSum = max(maxSum, currentSum); } return maxSum; } };
Dry Run Walkthrough
Let’s dry run a smaller case:
nums = [5, -2, 3, -1]
Start:
currentSum = 5
maxSum = 5
Index 1:
currentSum = max(-2, 5 - 2) = 3
maxSum = 5
Index 2:
currentSum = max(3, 3 + 3) = 6
maxSum = 6
Index 3:
currentSum = max(-1, 6 - 1) = 5
maxSum = 6
Answer = 6
Edge Cases
All negative numbers:
[-3, -1, -2]
Kadane still works because we initialize with nums[0].
Answer = -1
Single element:
[7]
Answer = 7
Large negatives breaking sequence:
[4, -100, 5]
Algorithm correctly restarts at 5.
Common Mistakes
Starting currentSum from 0 instead of nums[0].
This breaks all negative cases.
Forgetting to update maxSum at every step.
Trying to track subarray manually without understanding reset logic.
Intuition in One Line
Keep adding while it helps, reset when it hurts.
Time and Space Complexity
Time Complexity: O(n)
We traverse the array once.
Space Complexity: O(1)
No extra space used.
Real World Analogy
Imagine tracking your daily profit and loss.
If you are in profit, you continue.
If losses exceed your gains, you restart tracking from today.
You always keep the best profit seen so far.
That’s Kadane.
Where This Helps
This pattern appears in:
Maximum profit problems
Stock trading variations
Dynamic programming optimizations
Prefix sum optimizations
Summary
Kadane’s Algorithm is about making a local decision at each step.
Either extend your current subarray or start fresh.
By doing this greedily, you guarantee the optimal solution in linear time.
Once you understand this deeply, many DP problems start feeling simpler.