More
    AlgorithmsKadane's Algorithm for Maximum Sum Subarray

    Kadane’s Algorithm for Maximum Sum Subarray

    Write an efficient program to find the sum of subarray (Not subsequence) within a 1-D array of numbers that has the largest sum out of all other combinations.

    Naïve approach to this problem would be to maintain a variable to account for the maximum sum, and iterate the array with a nested loop. This would take O(N2) time to iterate throughout the array.

    Kadane’s Algorithm:

    The basic idea of Kadane’s Algorithm is to create two variables, one to store the maximum sum so far, and the other to check for the sum till the specific index. Whenever we get the sum till the index greater than the maximum sum so far, we update the maximum sum so far, and in case, sum till the index becomes < 0, we initialize sum till index as 0, because, there is not point in starting a range of subarray with negative numbers at the beginning.

    Let us understand it with a pseudo code and a dry run of the program,

    Initialize Variables:
    max_sum_so_far = INT_MIN
    max_sum_ending_here = 0
    Loop for each element of the input array:
    Inside the loop, handle the conditions below,
    1. max_sum_ending_here = max_sum_ending_here + a[i]
    2. If (max_sum_so_far < max_sum_ending_here)
    max_sum_so_far = max_sum_ending_here
    3. If (max_sum_ending_here < 0)
    max_sum_ending_here = 0
    return max_sum_so_far
    

    Dry Run:

    Let’s take the example:
        {-4, -6, 8, -2, -4, 2, 10, -6}
    
        max_sum_so_far = INT_MIN
        max_sum_ending_here = 0
    
        for i=0, a[0] = -4
        max_sum_ending_here = max_sum_ending_here + (-4)
        Set max_sum_ending_here = 0 because max_sum_ending_here < 0
        and set max_sum_so_far = -4
    
        for i=1, a[1] =  -6
        max_sum_ending_here = max_sum_ending_here + (-6)
        Since max_sum_ending_here = -6 and max_sum_so_far = -4, max_sum_so_far will remain -4
        Set max_sum_ending_here = 0 because max_sum_ending_here < 0
          
        
        for i=2, a[2] =  8
        max_sum_ending_here = max_sum_ending_here + (8)
        max_sum_ending_here = 8
        max_sum_so_far is updated to 8 because max_sum_ending_here greater 
        than max_sum_so_far which was -4 till now
    
        for i=3, a[3] =  -2
        max_sum_ending_here = max_sum_ending_here + (-2)
        max_sum_ending_here = 6
    
        for i=4, a[4] =  -4
        max_sum_ending_here = max_sum_ending_here + (-4)
        max_sum_ending_here = 2
    
        for i=5, a[5] =  2
        max_sum_ending_here = max_sum_ending_here + (2)
        max_sum_ending_here = 4
    
        for i=6, a[6] =  10
        max_sum_ending_here = max_sum_ending_here + (10)
        max_sum_ending_here = 14
        max_sum_so_far is updated to 14 because max_sum_ending_here is 
        greater than max_sum_so_far
    
        for i=7, a[7] =  -6
        max_sum_ending_here = max_sum_ending_here + (-6)
        max_sum_ending_here = 8
    
    Finally, after the loop terminates, the variables 
    max_sum_so_far = 14
    max_sum_ending_here = 8
    Hence, the final answer returned would be 14
    

    The pseudo code above works only when there is at least one positive integer in the input array. In case of all negative numbers, the code would return the element at index 0.

    In C++:

    // C++ program to print largest contiguous array sum
    #include<iostream>
    #include<climits>
    using namespace std;
    
    int maxSubArraySum(int a[], int size)
    {
    	int max_so_far = INT_MIN, max_ending_here = 0;
    
    	for (int i = 0; i < size; i++)
    	{
    		max_ending_here = max_ending_here + a[i];
    		if (max_so_far < max_ending_here)
    			max_so_far = max_ending_here;
    
    		if (max_ending_here < 0)
    			max_ending_here = 0;
    	}
    	return max_so_far;
    }
    
    /*Driver program to test maxSubArraySum*/
    int main()
    {
    	int a[] = {-4, -6, 8, -2, -4, 2, 10, -6};
    	int n = sizeof(a)/sizeof(a[0]);
    	int max_sum = maxSubArraySum(a, n);
    	cout << "Maximum contiguous sum is " << max_sum;
    	return 0;
    }
    

    In Java:

    import java.io.*;
    // Java program to print largest contiguous array sum
    import java.util.*;
    
    class Kadane
    {
    	public static void main (String[] args)
    	{
    		int [] a = {-2, -3, 4, -1, -2, 1, 5, -3};
    		System.out.println("Maximum contiguous sum is " +
    									maxSubArraySum(a));
    	}
    
    	static int maxSubArraySum(int a[])
    	{
    		int size = a.length;
    		int max_so_far = Integer.MIN_VALUE, max_ending_here = 0;
    
    		for (int i = 0; i < size; i++)
    		{
    			max_ending_here = max_ending_here + a[i];
    			if (max_so_far < max_ending_here)
    				max_so_far = max_ending_here;
    			if (max_ending_here < 0)
    				max_ending_here = 0;
    		}
    		return max_so_far;
    	}
    }

    Output:

    Maximum contiguous sum is 14

    Time Complexity would be O(N) and Auxiliary Space requirement is O(1).

    We can also maintain the indices of the subarray by creating the variables to store the indices whenever we get the maximum sum.

    Another implementation of Kadane’s algorithm is to use Dynamic Programming. The space and time complexity would remain same for DP based implementation, but the case when all numbers are negative would be handled correctly.

    We can also use a flag and a variable to store the maximum negative integer to handle the case when there are all negative integers in the array. This would not affect time complexity of the program.

    Iterative implementation of Kadane’s Algorithm for handling the case when there is no positive integer in the array.

    import java.util.*;
    import java.io.*;
    
    public class ProgramJava {
    
        static int maxSubArraySum(int a[]) {
            int size = a.length;
            int negativesCount = 0;
            boolean flag = false;
            int maxNegative = Integer.MIN_VALUE;
            int max_so_far = Integer.MIN_VALUE, max_ending_here = 0;
    
            for (int i = 0; i < size; i++) {
                max_ending_here = max_ending_here + a[i];
                if (max_so_far < max_ending_here)
                    max_so_far = max_ending_here;
                if (max_ending_here < 0)
                    max_ending_here = 0;
                if (a[i] < 0) {
                    negativesCount++;
                    maxNegative = Math.max(maxNegative, a[i]);
                }
            }
    
            if (negativesCount == size) flag = true;
    
            if (flag) return maxNegative;
            else return max_so_far;
        }
    
        public static void main(String[] args) throws IOException {
    
            int[] arr = {-8, -2, -3, -4, -7};
            int n = arr.length;
    
            System.out.println(maxSubArraySum(arr));
            
        }
    }

    Output:

    -2

    Time Complexity: O(N)

    Space Complexity: O(1)

    Sponsored

    Previous articleRadix Sort
    Next articleBellman Ford Algorithm

    1 COMMENT

    LEAVE A REPLY

    Please enter your comment!
    Please enter your name here

    Subscribe Today

    GET EXCLUSIVE FULL ACCESS TO PREMIUM CONTENT

    Get unlimited access to our EXCLUSIVE Content and our archive of subscriber stories.

    Exclusive content

    Latest article

    More article