Kadane 's Algorithm in java

Kadane algorithm is a famous algorithm to solve maximum subarray problem.

Maximum subArray problem: 

From Wikipedia :
In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.

Kadane 's Algorithm can be used to solve maximum sub array problem

Kadane's algorithm:

  • Initialize maxSoFar= 0 and maxEndingHere = 0 
  • Iterate over each element of the array 
    • maxEndingHere = maxEndingHere + a[i] 
    • if(maxEndingHere < 0) 
      •  maxEndingHere = 0 
    • if(maxSoFar < maxEndingHere) 
      •  maxSoFar = maxEndingHere 
    • return maxSoFar
Java Code:
// Kadane's Algorithm
public int kandaneForMaxSubArray(int[] arr) {
  int maxEndHere = 0;
  int maxSoFar = 0;
  for (int i = 0; i < arr.length; i++) {
   maxEndHere += arr[i];
   if (maxEndHere < 0) {
    maxEndHere = 0;
   }
   if (maxSoFar < maxEndHere) {
    maxSoFar = maxEndHere;
   }
  }
  return maxSoFar;
 }
Above algorithm won't work if all elements of array are negative. We will make small changes to algorithm to make it work for negative numbers for too.

Modified Kadane's algorithm:

  • Initialize maxSoFar= arr[0] and maxEndingHere = arr[0] 
  • Iterate over each element of the array 
    • maxEndingHere =Max of (arr[i], maxEndHere+arr[i])
    • if(maxSoFar < maxEndingHere) 
      •  maxSoFar = maxEndingHere 
    • return maxSoFar
Java code:
/* Modified Kadane's algorithm
 * If you make small modification to above algorithm
 * It will work for negative numbers too
*/
 public int kandaneForMaxSubArrayForNegativ(int[] arr) {
  int maxEndHere = arr[0];
  int maxSoFar = arr[0];
  for(int i=1;i<arr.length;i++){
   maxEndHere = Math.max(arr[i], maxEndHere+arr[i]);
   maxSoFar = Math.max(maxSoFar,maxEndHere);
  }
  return maxSoFar;
 }

Kadane Algorithm in java

package org.arpit.java2blog;
public class MaximumSubArrayMain {
 
 /* Kadane algorithm
  * It won't work when all elements of array are negative
  */
 public int kandaneForMaxSubArray(int[] arr) {
  int maxEndHere = 0;
  int maxSoFar = 0;
  for (int i = 0; i < arr.length; i++) {
   maxEndHere += arr[i];
   if (maxEndHere < 0) {
    maxEndHere = 0;
   }
   if (maxSoFar < maxEndHere) {
    maxSoFar = maxEndHere;
   }
  }
  return maxSoFar;
 }

/* Modified Kadane's algorithm
 * If you make small modification to above algorithm
 * It will work for negative numbers too
*/
 public int kandaneForMaxSubArrayForNegativ(int[] arr) {
  int maxEndHere = arr[0];
  int maxSoFar = arr[0];
  for(int i=1;i<arr.length;i++){
   maxEndHere = Math.max(arr[i], maxEndHere+arr[i]);
   maxSoFar = Math.max(maxSoFar,maxEndHere);
  }
  return maxSoFar;
 }

 public static void main(String args[]) {
  int arr[] = { 1, 8, -3, -7, 2, 7, -1, 9 };
  MaximumSubArrayMain maxSum = new MaximumSubArrayMain();
  System.out.println("Maximum subarray is  " + maxSum.kandaneForMaxSubArray(arr));
  int arrNeg[] = { -10, -8, -3, -7, -2, -7, -3, -9 };
  System.out.println("Maximum Subarray when all elements are negative : " + maxSum.kandaneForMaxSubArrayForNegativ(arrNeg));
 }
}
When you run above program, you will get below output:
Maximum subarray is  17
Maximum Subarray when all elements are negative : -2

Written by Arpit:

If you have read the post and liked it. Please connect with me on Facebook | Twitter | Google Plus

 

Java tutorial for beginners Copyright © 2012