- 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)
- Calculate sum at each index.
- 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