.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)
