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:

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:

Kadane Algorithm in java

When you run above program, you will get below output:

Add Comment