The idea behind this algorithm is quite simple. The algorithm begins by setting the maximum sum of a subarray to 0, since a subarray can also be a null set (this initialization is required to maximize the subarray sum if all the element of the array are negative). The algorithm also keeps track of the sum obtained at all the positions when it runs through the integers of the array sequentially; this is done for the possibility of maximizing the overall sum.
Note : The maximum sum at the current poition can and should not go below zero as the sum of 0 can always be obtained from a subarray of size null.
This algorithm is also known as Kadane’s algorithm.
Algorithm : Maximum sum subarray
Example of finding the maximum sum of a sub-array in an array Consider the array [ 5, -2 , 3, -8, 1, 6, -9 ]
| Current position | Number at current position | Maximum sum at current position | Maximum sum overall |
|---|---|---|---|
| - | - | Initialized to 0 | Initialized to 0 |
| 0 | -4 | maxsum_at_current_pos = -4 + 0 = -4Since -4 < 0, max sum at current position stays at 0 | maxsum_overall stays at 0 |
| 1 | 5 | maxsum_at_current_pos = 5 + 0 = 5Since 5 > 0, max sum at current position is changed to 5 | Since maxsum_at_current_pos (5) > (0) maxsum_overall, maxsum_overall is updated to 5 |
| 2 | -2 | maxsum_at_current_pos = -2 + 5 = 3Since 3 > 0, max sum at current position is changed to 3 | Since maxsum_at_current_pos (3) < (5) maxsum_overall, maxsum_overall stays at 5 |
| 3 | 3 | maxsum_at_current_pos = 3 + 3 = 6Since 6 > 0, max sum at current position is changed to 6 | Since maxsum_at_current_pos (6) > (5) maxsum_overall, maxsum_overall is updated to 6 |
| 4 | -8 | maxsum_at_current_pos = -8 + 6 = -2Since -2 < 0, max sum at current position is changed to 0 | maxsum_overall stays at 6 |
| 5 | 1 | maxsum_at_current_pos = 1 + 0 = 1Since 1 > 0, max sum at current position is changed to 1 | Since maxsum_at_current_pos (1) < (6) maxsum_overall, maxsum_overall stays at 6 |
| 6 | 6 | maxsum_at_current_pos = 6 + 1 = 7Since 7 > 0, max sum at current position is changed to 7 | Since maxsum_at_current_pos (7) > (6) maxsum_overall, maxsum_overall is updated to 7 |
| 7 | -9 | maxsum_at_current_pos = -9 + 7 = -2Since -2 < 0, max sum at current position is changed to 0 | maxsum_overall stays at 7 |
Time Complexity of finding the maximum sum of a subarray : O(n), where n is the number of elements in a subarray.
Java
import java.util.Arrays;
import java.util.List;
class Main {
static int Maximum_SubArraySum(List<Integer> array) {
int maxsum_at_current_pos = 0;
int maxsum_overall = 0;
for (Integer num : array) {
maxsum_at_current_pos = num + maxsum_at_current_pos;
if (maxsum_at_current_pos > maxsum_overall) {
maxsum_overall = maxsum_at_current_pos;
} else if (maxsum_at_current_pos < 0) {
maxsum_at_current_pos = 0;
}
}
return maxsum_overall;
}
public static void main(String args[])
{
List<Integer> arr1 = Arrays.asList(-4, 5, -2 , 3, -8);
System.out.print("Array 1 : [ ");
for(Integer element : arr1)
System.out.print(element + " ");
System.out.println("], Maximum sum of sub-array : " + Maximum_SubArraySum(arr1));
List<Integer> arr2 = Arrays.asList(-4, 5, -2 , 3, -8, 1, 6, -9);
System.out.print("Array 2 : [ ");
for(Integer element : arr2)
System.out.print(element +" ");
System.out.println("], Maximum sum of sub-array : " + Maximum_SubArraySum(arr2));
}
}
Output of maximum sum sub-array implemented in Java
Array 1 : [ -4 5 -2 3 -8 ], Maximum sum of sub-array : 6
Array 2 : [ -4 5 -2 3 -8 1 6 -9 ], Maximum sum of sub-array : 7
C++
#include<iostream>
#include<vector>
using namespace std;
int Maximum_SubArraySum(vector<int>& array) {
int maxsum_at_current_pos = 0;
int maxsum_overall = 0;
for (auto& num : array) {
maxsum_at_current_pos = num + maxsum_at_current_pos;
if (maxsum_at_current_pos > maxsum_overall) {
maxsum_overall = maxsum_at_current_pos;
} else if (maxsum_at_current_pos < 0) {
maxsum_at_current_pos = 0;
}
}
return maxsum_overall;
}
int main()
{
vector<int> arr1 = { -4, 5, -2 , 3, -8 };
cout << "Array 1 : [ ";
for(auto& element : arr1)
cout << element <<" ";
cout << "], Maximum sum of sub-array : " << Maximum_SubArraySum(arr1) << endl;
vector<int> arr2 = { -4, 5, -2 , 3, -8, 1, 6, -9 };
cout << "Array 2 : [ ";
for(auto& element : arr2)
cout << element <<" ";
cout << "], Maximum sum of sub-array : " << Maximum_SubArraySum(arr2) << endl;
return 0;
}
Output of maximum sum sub-array implemented in C++
Array 1 : [ -4 5 -2 3 -8 ], Maximum sum of sub-array : 6
Array 2 : [ -4 5 -2 3 -8 1 6 -9 ], Maximum sum of sub-array : 7
Python : Maximum sum sub-array in Python
#!/usr/bin/python3
def Maximum_SubArraySum (array):
maxsum_at_current_pos = 0
maxsum_overall = 0
for num in array:
maxsum_at_current_pos = num + maxsum_at_current_pos;
if (maxsum_at_current_pos > maxsum_overall):
maxsum_overall = maxsum_at_current_pos
elif (maxsum_at_current_pos < 0):
maxsum_at_current_pos = 0
return maxsum_overall
arr1 = [ -4, 5, -2 , 3, -8 ];
print ("Array 1:", *arr1)
print ("Maximum sum of sub-array : ", Maximum_SubArraySum(arr1))
arr2 = [ -4, 5, -2 , 3, -8, 1, 6, -9 ];
print ("Array 2:", *arr2)
print ("Maximum sum of sub-array : ", Maximum_SubArraySum(arr2))
Output of maximum sum sub-array implemented using Python
Array 1: -4 5 -2 3 -8
Maximum sum of sub-array : 6
Array 2: -4 5 -2 3 -8 1 6 -9
Maximum sum of sub-array : 7