Maximum sum contiguous sub-array

Problem statement – Given an array, find a contiguous sub-array whose sum is maximum. More precisely, if we have an array A[0, 1, 2 … N], we need to find a sub-array A[i, i + 1, i + 2, … j] such that the sum of elements in the sub-array is maximum.

Clues –

• Your solution should be O(N) in time and O(1) in space.
• Can you think of a solution which solves the problem in a single scan of the array?

Solution – This is a popular interview question asked by the interviewers to test the basics of the candidate. This problem can be solved in O(N) time by using Kadane’s Algorithm. In this algorithm, we keep adding elements to a sum variable as we are traversing the array. This sum variable holds the sum of a sub-array. When the sum variable becomes negative, we cast off the the sub-array seen so far and reset sum variable. The final answer will be the maximum of all the values which were stored in sum over all iterations.

Example – For the array A = [-2 , 1, -3, 4, -1, 2, 1, -5, 4]

Code –

public class Solution {
	public int maxSubArray(List<Integer> a) {
	    int sum = 0;
	    int maxSum = Integer.MIN_VALUE;
	    
	    for (int i = 0; i < a.size(); ++i) {
	        if (sum + a.get(i) < 0) {
	            // Adding this element will make the current
	            // subarray sum negative, so don't add this element
	            // and start a new subarray with next element
	            sum = 0;
	        } else {
	            // Adding this element will increase the
	            // current subarray sum, so add this
	            // element to the current subarray
	            sum += a.get(i);
	        }
	        
	        // maxSum is the maximum of -
	        //
	        // 1. maxSum so far
	        // 2. if sum == 0, then a.get(i) which is proably a -ve number
	        // 3. if sum != 0, then sum of subarray so far
	        maxSum = Math.max(maxSum, sum == 0 ? a.get(i) : sum);
	    }
	    
	    return maxSum;
	}
}

If you didn’t understand why we need the “sum == 0 ? a.get(i) : sum” condition in the end, think of the case where array A = [-3, -2, -1]. Basically when the array has all negative values, you’d want to return the largest among the negative values. Now remember, sum variable doesn’t store negative values, so when it holds 0, we consider A[i] instead of sum. Give it a little thought, I’m sure you’ll understand it. If you need a more explanation, refer to my post on Kadane’s Algorithm.