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