code_blocks Window Visualizer
Max Window
-2
0
1
1
-3
2
4
3
-1
4
2
5
1
6
-5
7
4
8
Current Window
arrow_upward
i
Current Window Sum
-2
Global Max Sum
-2
Best so far
Initialization
Ready to start. We will initialize our trackers using the first element of the array.
terminal Source Code
C++int maxSubArray(vector<int>& nums) {
int current_sum = nums[0];
int max_so_far = nums[0];
for (int i = 1; i < nums.size(); i++) {
// Start new or extend?
current_sum = max(nums[i], current_sum + nums[i]);
// Check global max
if (current_sum > max_so_far) {
max_so_far = current_sum;
}
}
return max_so_far;
}
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
#
Current Window Elements
#
Global Max Window Found
psychology Understanding the Logic
The beauty of Kadane's algorithm lies in its greedy decision at Line 7. At each position i, we ask a simple question:
"Is the number nums[i] itself larger than the sum we've been building plus nums[i]?"
-
check_circle
If yes, the previous history is a burden (negative sum). We discard it and start a new subarray at
i. -
cancel
If no, the previous history contributes positively (or we are forced to take a small dip to reach a larger number later). We extend the subarray.