Largest sum contiguous subarray

Largest sum subarray (Kadane’s algorithm)

Given an array of integers (positive and negative), find largest sum subarray, that is contiguous elements in array, which add up to maximum sum. This problem is solved using Kadane’s algorithm. For example, for array {-1, 3, -5, 4, 6, -1, 2, -7, 13, -3}, largest sum subarray will be {4,6,-1,2,-7,13} with sum = 17.

What will be the brute force solution, without considering any time complexity? Well, scan all the subarrays of array and take the one which has the maximum sum. How many such subarrays can be there? If size of array is n, n * (n -1 ) / 2 subarrays, hence complexity of brute solution will O(n2)

package com.company;

/**
	* Created by sangar on 20.8.18.
	*/
public class KadaneAlgorithm {
	public static int largestSumSubarray (int[] a){
		int maxSum = Integer.MIN_VALUE;

		for(int i=0; i < a.length; i++){
			int currentSum = 0;
			for(int j=i; j < a.length; j++){
				currentSum+= a[j];
				if(maxSum < currentSum){
					maxSum = currentSum;
				}
			}
		}
		return maxSum;
	}
	public static void main(String args[]) {
		int[] a = {-1, 3, -5, 4, 6, -1, 2, -7, 13, -3};
		System.out.println(largestSumSubarray(a));
	}
}

Maximum sum subarray with dynamic programming

Dynamic programming builds solutions from the bottom up by breaking each problem down into smaller, problems that you solve first. Recursion also breaks problems down into subproblems but does this from the top down. One advantage of dynamic programming over recursion is that it prevents possible duplicate solutions of the same subproblem, which uses less CPUs and generally makes your code run faster.

Code Chef Wiki

How can we fill create the solution bottom up? Consider a case where there is only one element in the array. What will be the largest sum subarray? Haha, it the element itself. 
Assume now, that there is one more element in the same array, what will be the condition that you will include the second element into largest sum subarray? Obviously, if adding the second element increase the previous sum.

Also, there is a possibility that the second element itself is the largest sum subarray or it starts from the second element. If the first number was negative and the second one is positive, the second number itself is bigger than the sum, no matter what. So, the second element becomes the current sum.

Rule is that, at each element j, take the maximum of sum of the current element and accumulated sum till previous index and current element.

current_sum  = max ( current_sum + A[j], A[j])

Now, you have the current sum at element A[j], see if it is greater than global maximum till now? If yes, replace global maximum with current sum.

if(maxSum < currentSum )
	maxSum = currentSum;

Let’s see how this algorithm works with an example. we have an array as [-1, 4, 2, -1]

  1. Set a maxSum and currentSum, both equal to first element of array to start
  2. Now, look at the next element which is 4, so subarray under consideration is [-1, 4], the maximum is either current element or is the sum of the current element plus the previous maximum (-1 + 4 = 3)
  3. Since 4 > 3, the currentSum is 4, and since 4 > -1, we can update the maxSum as well
  4. With the value of the next index (2), the maximum is either 2 or is the sum of the current element plus the previous maximum (4 + 2 = 6)
  5. Next element is -1, which is less than currentSum, so currentSum remains as it is, so is maxSum.

Hope this example helps to understand the beauty of this Kadane’s algorithm to find largest sum subarray in an array.

Kadane’s algorithm does not work with an array with all elements being negative. What we can do is that scan all elements of array prior to application of algorithm and if there is at least one positive number. Also during this phase keep track of the largest number seen. If all elements are negative, just return largest number.

Largest sum subarray : Kadane’s algorithm implementation

package com.company;

/**
	* Created by sangar on 20.8.18.
*/
public class KadaneAlgorithm {
	public static int kadaneAlgorithm (int[] a){
		int maxSum = a[0];
		int currentSum = a[0];
		
		for(int i=1; i<a.length; i++) {
			currentSum = Integer.max(a[i], currentSum + a[i]);
			if (maxSum < currentSum) {
				maxSum = currentSum;
			}
		}
		return maxSum;
	}
	public static void main(String args[]) {
		int[] a = {-1, 3, -5, 4, 6, -1, 2, -7, 13, -3};
		System.out.println(kadaneAlgorithm(a));
	}
}

Complexity of finding largest sum subarray in an array is O(N) in time and O(1) in space.

Please share if there is something wrong or missing. If you are interested in contributing to website, please reach out to us at communications@algorithmsandme.com

References:

  • https://www.codechef.com/wiki/tutorial-dynamic-programming
  • https://www.hackerrank.com/challenges/maxsubarray/problem