Maximum subarray sum

Given an array of unordered positive and negative integers, find the maximum subarray sum in the array.
For example:
Array: {2, -9, 5, 1, -4, 6, 0, -7, 8}
Output:
Maximum subarray sum is 9


Video coming soon!



Subscribe for more updates


Algorithm/Insights

1. Start with curSum = 0 and maxSum = 0.
2. Traverse the array elements, from i = 0 to n-1, where n is the length of the array.
   a. Keep adding array elements to curSum till curSum >= 0 and update maxSum to curSum if maxSum < curSum.
   b. As soon as curSum becomes < 0, reset curSum = 0.
3. Finally return maxSum.
This is known as Kadane's algorithm.

The above method does not take care of the case when all the elements in the array are negative.
In this case, we can modify the algorithm, to keep a flag hasAllNegativeNumbers initialized to true.
If a positive or 0 element is seen in the array, then set hasAllNegativeNumbers = false.
Also, while traversing the array, keep track of maximum negative element.
Finally, if hasAllNegativeNumbers is true, then return maxNegativeSum, else return maxSum.


Algorithm Visualization




Code Snippet

			
package com.ideserve.questions.saurabh;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Given an array of unordered positive and negative integers,
 * find the maximum subarray sum in the array.
 *
 * @author Saurabh
 */
public class MaxSubarraySum {

	public static int findMaxSubarraySum(int[] input) {
		int curSum = 0;
		int maxSum = 0;
		boolean hasAllNegativeNumbers = true;
		int maxNegativeSum = Integer.MIN_VALUE;
		for(int i = 0; i < input.length; i++) {
			if(hasAllNegativeNumbers && input[i] >= 0) {
				hasAllNegativeNumbers = false;
			} else if(hasAllNegativeNumbers && input[i] < 0 && maxNegativeSum < input[i]) {
				maxNegativeSum = input[i];
			}
			
			curSum += input[i];
			if(curSum < 0) {
				curSum = 0;
			}
			if(maxSum < curSum) {
				maxSum = curSum;
			}
		}
		return hasAllNegativeNumbers ? maxNegativeSum : maxSum;
	}
	
	public static void main(String[] args) {
		int[] input = {2, -9, 5, 1, -4, 6, 0, -7, 8};
		System.out.println("Maximum subarray sum is " + findMaxSubarraySum(input));
	}
}
		

Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(1)


Contribution

  • Sincere thanks from IDeserve community to Saurabh Kumar for compiling current post.

    Saurabh Kumar

    Ninja Programmer