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

Finding the maximum sum of a subarray in an array

Key points of Kadane’s algorithm

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

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