Kadane’s Algorithm
Kadane's algorithm is a greedy/dynamic programming algorithm that can be used on array problems to bring the time complexity down to O(n). It is used to calculate the maximum sum subarray ending at a particular position.
Problem Statement
Given an integer array arr, find the contiguous subarray (containing at least one number) which has the largest sum and returns its sum.
Intuition
The question above is asking us to find a group of contiguous values in an array that give the largest sum. We are then asked to return that sum. If we forget about Kadane's algorithm for a second, the brute force way to approach this would be to go through every single subarray and calculate the sum, while keeping track of a maximum sum. This will work but there is a lot of repeated work. For every iteration of our outer for loop, our inner loop does linear work. This makes the complexity 𝑂(𝑛^2).
Brute Force Approach
def bruteForce(nums):
maxSum = nums[0]
for i in range(len(nums)):
curSum = 0
for j in range(i, len(nums)):
curSum += nums[j]
maxSum = max(maxSum, curSum)
return maxSum
Optimized Approach - Kadane’s Algorithm
The intuition of the algorithm is not to consider the subarray as a part of the answer if its sum is less than 0. A subarray with a sum less than 0 will always reduce our answer and so this type of subarray cannot be a part of the subarray with maximum sum.
Here, we will iterate the given array with a single loop and while iterating we will add the elements in a sum variable. Now, if at any point the sum becomes less than 0, we will set the sum as 0 as we are not going to consider any subarray with a negative sum. Among all the sums calculated, we will consider the maximum one.
Thus we can solve this problem with a single loop.
Pseudocode for Kadane’s Algorithm
Initialize:
- max_so_far = INT_MIN
- max_ending_here = 0
Loop for each element of the array
- (a) max_ending_here = max_ending_here + a[i]
- (b) if(max_so_far < max_ending_here) max_so_far = max_ending_here
- (c) if(max_ending_here < 0) max_ending_here = 0 return max_so_far
Implementing Kadane’s Algorithm
Python Implementation
import sys
def maxSubarraySum(arr, n):
maxi = -sys.maxsize-1 # maximum sum
sum = 0
for i in range(n):
sum += arr[i]
if sum > maxi:
maxi = sum
# If sum < 0: discard the sum calculated
if sum < 0:
sum = 0
# To consider the sum of the empty subarray
# uncomment the following check:
#if maxi < 0: maxi = 0
return maxi
Java Implementation
import java.util.*;
public class Main {
public static long maxSubarraySum(int[] arr, int n) {
long maxi = Long.MIN_VALUE; // maximum sum
long sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
if (sum > maxi) {
maxi = sum;
}
// If sum < 0: discard the sum calculated
if (sum < 0) {
sum = 0;
}
}
// To consider the sum of the empty subarray
// uncomment the following check:
//if (maxi < 0) maxi = 0;
return maxi;
}
public static void main(String args[]) {
int[] arr = { -2, 1, -3, 4, -1, 2, 1, -5, 4};
int n = arr.length;
long maxSum = maxSubarraySum(arr, n);
System.out.println("The maximum subarray sum is: " + maxSum);
}
}
C++ Implementation
long long maxSubarraySum(int arr[], int n) {
long long maxi = LONG_MIN; // maximum sum
long long sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
if (sum > maxi) {
maxi = sum;
}
// If sum < 0: discard the sum calculated
if (sum < 0) {
sum = 0;
}
}
// To consider the sum of the empty subarray
// uncomment the following check:
//if (maxi < 0) maxi = 0;
return maxi;
}
JavaScript Implementation
function maxSubarraySum(arr, n) {
let maxi = Number.MIN_SAFE_INTEGER; // maximum sum
let sum = 0;
for (let i = 0; i < n; i++) {
sum += arr[i];
if (sum > maxi) {
maxi = sum;
}
// If sum < 0: discard the sum calculated
if (sum < 0) {
sum = 0;
}
}
// To consider the sum of the empty subarray
// uncomment the following check:
//if (maxi < 0) maxi = 0;
return maxi;
}
Complexity Analysis
Time Complexity :
- , We are using a single loop running N times.
Space Complexity
- , as Only Variables are used.
Conclusion
- Kadane's algorithm offers a straightforward and efficient approach to solving the maximum sum subarray problem, making it a fundamental technique in algorithmic problem-solving and data analysis.