Refer the problem statement: Maximum Subarray Sum

Let us try to understand how Kadane’s Algorithm work. This solution is similar to sliding window in a way.

Pseudocode

For at-least 1 non-negative numbers

Here’s the pseudocode for Kadane’s algorithm based on your template, designed to handle arrays with non-negative sums:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

# Start
maxGlobal <- 0
maxCurrent <- 0

# Loop over array
for i from 0 to n-1 do
	maxCurrent <- maxCurrent + a[i]
 
	# If maxCurrent drops below 0, reset it to 0
	if maxCurrent < 0 then
		maxCurrent <- 0
	end if
 
	# Update maxGlobal if we've found a new maximum
	if maxGlobal < maxCurrent then
		 maxGlobal <- maxCurrent
	end if
end for

maxGlobal is sometimes denoted as maxSoFar and maxCurrent is denoted as maxEndingHere.

Please note that the above pseudocode initializes maxGlobal and maxCurrent to 0, which assumes there will be at least one non-negative number in the input array.

We can rewrite it as (removing if condition and using max() function instead):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

maxGlobal <- 0
maxCurrent <- 0

# Loop over array
for i from 0 to n-1 do
	maxCurrent <- maxCurrent + a[i]
 
	maxCurrent <- max(0, maxCurrent)
	maxGlobal <- max(maxGlobal, maxCurrent)
end for

For all negative number

If the array can be entirely negative, the initialization should be changed to handle this by setting maxGlobal and maxCurrent to the first element of the array or to negative infinity to correctly find the maximum subarray sum, which might still be negative.

Here’s the adjusted pseudocode for arrays that could contain all negative numbers:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

maxGlobal <- a[0] # or alternatively, maxGlobal <- -∞ for empty subarray sum
maxCurrent <- a[0] # or alternatively, maxCurrent <- -∞ for empty subarray sum


for i from 1 to n-1 do
	maxCurrent <- max(maxCurrent + a[i], a[i])
	maxGlobal <- max(maxGlobal, maxCurrent)
end for

return maxGlobal

So we made 2 changes:

  • Initial maxGlobal and maxCurrent with a[0]
  • Instead of updating maxCurrent to 0, we update with arr[i] in case of max.

Code

Original

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public int maxSubArray(int[] nums) {
	int maxSoFar = 0;
	int maxEndingHere = 0;

	for (int i = 0; i < nums.length; i++) {
		maxEndingHere += nums[i];

		if (maxEndingHere < 0) {
			maxEndingHere = 0;
		}
		if (maxSoFar < maxEndingHere) {
			maxSoFar = maxEndingHere;
		}
	}

	return maxSoFar;
}

Modified Kadane

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

public static int maxSubArray(int[] nums) {
	int maxSoFar = nums[0];
	int maxEndingHere = nums[0];

	for (int i = 1; i < nums.length; ++i) {
		maxEndingHere = Math.max(maxEndingHere + nums[i], nums[i]);
		maxSoFar = Math.max(maxSoFar, maxEndingHere);
	}

	return maxSoFar;
}

Limitation of the Algorithm

So, remember to use modified Kadane’s algorithm, when the array contains only negative numbers. Original Kadane’s algorithm will return the value of the largest negative element rather than a sum, because the algorithm is designed to look for positive contiguous sequences. This may or may not be desired, depending on whether empty subarrays with a sum of 0 are considered valid.