Finding the maximum sum of a subarray in an array

• The algorithm begins by setting the maximum sum of a subarray to 0, since a subarray can also be a null set. The 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 each position 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 should not go below zero as the sum of 0 can always be obtained from a subarray of size 0.

Algorithm : Maximum sum subarray

1. Initialize the overall maximum sum of subarray and maximum sum obtained by adding the current element 0.
maxsum_overall = 0
maxsum_at_current_pos = 0
2. For each number num in the array :
a)     maxsum_at_current_pos = num + maxsum_at_current_pos
b)     If ( maxsum_at_current_pos > maxsum_overall ) then
c)         maxsum_overall = maxsum_at_current_pos
d)     Else if ( maxsum_at_current_pos < 0 ) then
e)         maxsum_at_current_pos = 0

Example
Consider the array [ -4, 5, -2 , 3, -8, 1, 6, -9 ]

Current
position
Number at
current position
Maximum sum at current position Maximum sum overall
( Initialized to 0 )
0 -4 maxsum_at_current_pos = -4 + 0 = -4
Since -4 < 0, max sum at current position stays at 0
maxsum_overall stays at 0
1 5 maxsum_at_current_pos = 5 + 0 = 5
Since 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 = 3
Since 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 = 6
Since 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 = -2
Since -2 < 0, max sum at current position is changed to 0
maxsum_overall stays at 6
5 1 maxsum_at_current_pos = 1 + 0 = 1
Since 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 = 7
Since 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 = -2
Since -2 < 0, max sum at current position is changed to 0
maxsum_overall stays at 7

Time complexity : O ( n ), where n is the number of elements in a subarray.

Maximum sum sub-array implementation

#!/usr/bin/python3
from typing import List # For annotations

def Maximum_SubArraySum (array : List[int]) -> int:

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

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
#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

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

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