Algotree > Algorithms > Dynamic Programming > Finding maximum sum of a subarray in an array

Finding maximum sum of a subarray in an array

Finding the maximum sum of a subarray in an array

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

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
For each number num in the array do :
3.     maxsum_at_current_pos = num + maxsum_at_current_pos
4.     If maxsum_at_current_pos > maxsum_overall
5.         maxsum_overall = maxsum_at_current_pos
6.     Else if maxsum_at_current_pos < 0
7.         maxsum_at_current_pos = 0

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 = -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 of finding the maximum sum of a subarray : O(n), where n is the number of elements in a subarray.

C++ : Implementation of maximum sum sub-array using dynamic programming in C++11

#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

Python : Implementation of maximum sum sub-array using dynamic programming in Python3

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

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