.png)
Kadane’s Algorithm (Maximum Subarray Sum)
Problem Statement
Given an array of integers (which may contain both positive and negative numbers), find the maximum possible sum of a contiguous subarray.
A contiguous subarray is a group of elements that are adjacent in the original array.
This problem is famously solved using Kadane’s Algorithm.
Example 1
Input
arr = [-2, -3, 4, -1, -2, 1, 5, -3]
Output
7
Explanation
The subarray [4, -1, -2, 1, 5] gives the maximum sum:
4 + (-1) + (-2) + 1 + 5 = 7
Example 2
Input
arr = [5, -2, 3, 4]
Output
10
Why Kadane’s Algorithm Is Important
Kadane’s Algorithm is one of the most frequently asked interview problems because it:
- Converts a brute-force problem into an optimal solution
- Introduces dynamic programming thinking
- Efficiently handles negative values
- Is used in:
- Stock price analysis
- Performance optimization
- Financial data processing
Core Idea of Kadane’s Algorithm
At every index, decide:
- Whether to extend the existing subarray
- Or start a new subarray from the current element
If the current sum becomes negative, it is better to discard it and start fresh.
Algorithm (Step-by-Step)
- Initialize:
- currentSum = 0
- maxSum = -∞
- Traverse the array:
- Add current element to currentSum
- Update maxSum
- If currentSum < 0, reset it to 0
- After traversal, maxSum holds the answer
Time and Space Complexity
- Time Complexity: O(n)
- Space Complexity: O(1)
C Implementation
#include<stdio.h>
#include<limits.h>
int main() {
int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
int n = sizeof(arr) / sizeof(arr[0]);
int currentSum = 0;
int maxSum = INT_MIN;
for(int i = 0; i < n; i++) {
currentSum += arr[i];
if(currentSum > maxSum)
maxSum = currentSum;
if(currentSum < 0)
currentSum = 0;
}
printf("Maximum Subarray Sum: %d", maxSum);
return 0;
}
Output
Maximum Subarray Sum: 7
C++ Implementation
#include <iostream>
#include <climits>
using namespace std;
int main() {
int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
int n = sizeof(arr) / sizeof(arr[0]);
int currentSum = 0;
int maxSum = INT_MIN;
for(int i = 0; i < n; i++) {
currentSum += arr[i];
maxSum = max(maxSum, currentSum);
if(currentSum < 0)
currentSum = 0;
}
cout << "Maximum Subarray Sum: " << maxSum;
return 0;
}
Output
Maximum Subarray Sum: 7
Java Implementation
public class KadaneAlgorithm {
public static void main(String[] args) {
int[] arr = {-2, -3, 4, -1, -2, 1, 5, -3};
int currentSum = 0;
int maxSum = Integer.MIN_VALUE;
for (int x : arr) {
currentSum += x;
maxSum = Math.max(maxSum, currentSum);
if (currentSum < 0)
currentSum = 0;
}
System.out.println("Maximum Subarray Sum: " + maxSum);
}
}
Output
Maximum Subarray Sum: 7
Python Implementation
arr = [-2, -3, 4, -1, -2, 1, 5, -3]
current_sum = 0
max_sum = float('-inf')
for x in arr:
current_sum += x
max_sum = max(max_sum, current_sum)
if current_sum < 0:
current_sum = 0
print("Maximum Subarray Sum:", max_sum)
Output
Maximum Subarray Sum: 7
JavaScript Implementation
let arr = [-2, -3, 4, -1, -2, 1, 5, -3];
let currentSum = 0;
let maxSum = -Infinity;
for (let x of arr) {
currentSum += x;
maxSum = Math.max(maxSum, currentSum);
if (currentSum < 0)
currentSum = 0;
}
console.log("Maximum Subarray Sum:", maxSum);
Output
Maximum Subarray Sum: 7
Dry Run Example
| Element | currentSum | maxSum |
|---|---|---|
| -2 | -2 → 0 | -2 |
| -3 | -3 → 0 | -2 |
| 4 | 4 | 4 |
| -1 | 3 | 4 |
| -2 | 1 | 4 |
| 1 | 2 | 4 |
| 5 | 7 | 7 |
| -3 | 4 | 7 |
Important Edge Case
When All Elements Are Negative
Example:
arr = [-5, -2, -8]
Output:
-2
Kadane’s Algorithm still works because maxSum is initialized with the smallest possible value.
Summary
- Kadane’s Algorithm finds the maximum subarray sum in linear time
- Works efficiently with negative numbers
- Requires no extra space
- A must-know algorithm for interviews
Key Takeaways
- Time Complexity: O(n)
- Space Complexity: O(1)
- Dynamic decision at each step
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
