Kadane algorithm is the fastest and optimized algorithm of Maximum Sum Subarray problem. Maximum sum subarray is the contiguous subarray within a given one dimension array with the largest sum. This problem is one of the classical interview questions in IT companies like Google, Apple, Amazon, LinkedIn, Facebook, Microsoft, Uber, and many more.
For example, for an array, a = [-2, -4, 4, -2, -1, 1, 5, -7]
A contiguous subarray = [4, -2, -1, 1, 5] gives the maximum sum of 7.
Application
Maximum sum subarray problem finds application in many fields like finance, genomic, sequence analysis and computer vision. One of the real life example of it is to find out a part of the year the company earns more income and how much it earns. It is also useful in analysis of genomic sequence to identify important biological segments of protein sequences. In computer vision, it is used to detect the brightest area in an image. Some other applications include GC-rich regions, DNA binding domains, low-complexity filter and regions of high charge.
Solution Algorithm
Several algorithmic techniques, including brute force, divide and conquer, dynamic programming, and reduction to the shortest paths can solve this problem. However, the fastest and most efficient algorithm is for solving it is Kadane algorithm. It has a time complexity of O(n) while divide and conquer algorithm which has a time complexity of O(n.log(n)) and brute force algorithm has time complexity of O(
)
Kadane Algorithm
Kadane algorithm is the most efficient algorithm for solving Maximum Subarray Problem. It has a time complexity of O(N). Idea of Kadane algorithm is very simple and elegant. It looks for all positive contiguous segments of the array and returns the maximum. Variable max_current stores the maximum value of current positive contiguous segment and max_so_far store the maximum of all the max_current.
Program
Python 3 Code
def maxSubArray(a):
size = len(a)
max_so_far = -1
max_current = 0
for i in range(size):
max_current = max_current + a[i]
# Updating max_so_far if max_current is greater than max_so_far
if (max_so_far < max_current):
max_so_far = max_current
# Resetting max_current to 0 if sum of current segment is -ve
if max_current < 0:
max_current = 0
return max_so_far
a = [-2, -4, 4, -2, -1, 1, 5, -7]
print("Maximum sum of contiguous subarray is: %d" %(maxSubArray(a)))
#------ Output -------
Maximum sum of contiguous subarray is: 7
Java Code
import java.io.*;
// Java program to prints the largest contiguous array sum
import java.util.*;
class Kadane
{
public static void main (String[] args)
{
int [] a = {-2, -4, 4, -2, -1, 1, 5, -7};
System.out.println("Maximum sum of contiguous subarray is: " +
maxSubArraySum(a));
}
static int maxSubArray(int a[])
{
int size = a.length;
int max_so_far = -1, max_current = 0;
for (int i = 0; i < size; i++)
{
max_current = max_current + a[i];
// Updating max_so_far if max_current is greater than max_so_far
if (max_so_far < max_current)
max_so_far = max_current;
// Resetting max_current to 0 if sum of current segment is -ve
if (max_ending_here < 0)
max_ending_here = 0;
}
return max_so_far;
}
}
//-------------Output------------------
Maximum sum of contiguous subarray is: 7
C++ Code
// C++ program to print largest contiguous array sum
#include<iostream>
#include<climits>
using namespace std;
int maxSubArraySum(int a[], int size)
{
int max_current = -1, max_ending_here = 0;
for (int i = 0; i < size; i++)
{
max_current = max_current + a[i];
//Updating max_so_far if max_current is greater than max_so_far
if (max_so_far < max_current)
max_so_far = max_current;
// Resetting max_current to 0 if sum of current segment is -ve
if (max_current < 0)
max_current = 0;
}
return max_so_far;
}
/*Driver program to test maxSubArraySum*/
int main()
{
int a[] = {-2, -4, 4, -2, -1, 1, 5, -7};
int n = sizeof(a)/sizeof(a[0]);
int max_sum = maxSubArraySum(a, n);
cout << "Maximum sum of contiguous subarray is: " << max_sum;
return 0;
}
//-------------Output------------------
Maximum sum of contiguous subarray is: 7
Request
If you find a problem with the current code or some other way to do that may be useful to others please comment it or mail it to [email protected]