Maximum subarray sum

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.

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)