Find maximum sum subarray in java using Kadane’s algorithm

• Given an array containing positive & negative integers.
• We would like to find subarray having maximum sum.
• We will use Kadane’s algorithm to find contiguous array having maximum sum.

Examples: maximum sum subarray in java using Kadane’s algorithm

Example 1

• Given an array { -2, 2, 1, -3, 1}
• Maximum sum array is {2,1} of sum = 3

Example 2

• Given an array { -2, 2, 3, -3, 4}
• Maximum sum array is {2, 3, -3, 4} of sum = 6

Example 3

• Given an array { 1 , 2, -4, 4, -1, -2, 4}
• Maximum sum array is {4, -1, -2, 4} of sum = 5

Kadane’s algorithm to find maximum sum subarray in java

• Given array need to have at-least one positive integer value.
  • { -2, -2, 3, -3, -4}
• Kadane algorithm does not work if array contains all negative numbers.
  • Special handling needs to be done (we will discuss it in a separate post).
• Initialize localMax = 0 (sum representing during iteration)
• Initialize maxSum = 0 (sum representing maximum sum sub array)
• Kadane’s algorithm iterate through the array values
  • Calculate sum at each index.
    • localMax = localMax + array[index];
  • If local sum is negative during iteration then reset max sum to zero.
    • localMax = Math.max(0, localMax)
  • Update the maximum sum of sub array if localMax is greater than maxSum.
    • maxSum = Math.max(maxSum, localMax)
• At end of iteration, we will get maximum sum subarray.

Time complexity of algorithm is O (n).

Program – maximum sum subarray in java using Kadane’s algorithm

package org.learn.arrays;

import java.util.Arrays;

public class KadaneMaxSumSubArray {

	private static void maxSubArray(int[] input) {
		
		int localMax = 0;
		int maxSum = Integer.MIN_VALUE;

		for (int index = 0; index < input.length; index++) {

			localMax = localMax + input[index];			
			localMax = Math.max(0, localMax);
			maxSum = Math.max(maxSum, localMax);
		}
		
		System.out.printf("%d",maxSum);
	}

	public static void main(String[] args) {

		int array[] = { -2, 2, 1, -3, 1};	
		String sArray = Arrays.toString(array);
		
		System.out.printf("1. Max sum sub array in %s is : ",sArray);
		maxSubArray(array);
		
		array = new int[]{ -2, 2, 3, -3, 4};	
		sArray = Arrays.toString(array);
		
		System.out.printf("\n2. Max sum sub array in %s is : ",sArray);
		maxSubArray(array);
		
		array = new int[]{ 1 , 2, -4, 4, -1, -2, 4};	
		sArray = Arrays.toString(array);
		System.out.printf("\n3. Max sum sub array in %s is : ",sArray);
		maxSubArray(array);
	}	
}

Output – maximum sum subarray in java using Kadane’s algorithm

1. Max sum sub array in [-2, 2, 1, -3, 1] is : 3
2. Max sum sub array in [-2, 2, 3, -3, 4] is : 6
3. Max sum sub array in [1, 2, -4, 4, -1, -2, 4] is : 5