Kadane’s Algorithm in Java

(Asked by all big gaint tech compaines like AMAZON, PAYTM, MICROSOFT,etc)

Basicly, kaden’s algorithm is used to find the longest sum contiguous subarray.

Algorithm:

Initialize:
    currentSum = 0
    maxSum = 0

Loop for each element of the array
  (a) currentSum = currenSum + a[i]
  (b) if(currentSum < 0)
            currentSum = 0
  (c) if(maxSum < currentSum)
            maxSum = currentSum
return maxSum


Explanation:

Simple idea of the Kadane’s algorithm is to look for all positive contiguous segments of the array (currentSum is used for this). And keep track of maximum sum contiguous segment among all positive segments (maxSum is used for this). Each time we get a positive sum compare it with maxSum and update maxSum if it is greater than maxSum and return it after iterating whole array.

Lets take the example:
    {-2, -3, 4, -1, -2, 1, 5, -3}

    maxSum = currentSum = 0

    for i=0,  a[0] =  -2
    currentSum = currentSum + (-2)
   currentSum = 0 because currentSum < 0

    for i=1,  a[1] =  -3
   currentSum = currentSum + (-3)
   currentSum = 0 because currentSum < 0

    for i=2,  a[2] =  4
    currentSum =  currentSum + (4)
   currentSum = 4
    maxSum is updated to 4 because currentSum greater 
    than maxSum which was 0 till now

    for i=3,  a[3] =  -1
    currentSum = currentSum + (-1)
    currentSum = 3

    for i=4,  a[4] =  -2
    currentSum = currentSum + (-2)
    currentSum = 1

    for i=5,  a[5] =  1
   currentSum = currentSume + (1)
    currentSum = 2

    for i=6,  a[6] =  5
    currentSum = currentSum + (5)
   currentSum = 7
    maxSum is updated to 7 because currentSum is 
    greater than maxSum

    for i=7,  a[7] =  -3
   currentSum = currentSum + (-3)
    currentSume = 4
After iterating all elemnts of array we will get the maxSum = 7 as above shown in the image. 

Code to find longest sum subArray (The implementation handles the case when all numbers in array are negative.).

import java.io.*; 
  
class Kaden's { 
  
    static int maxSubArraySum(int arr[], int n) 
    { 
    int maxSum = arr[0]; 
    int currentSum = arr[0]; 
  
    for (int i = 1; i < n; i++) 
    { 
           currentSum = Math.max(arr[i], currentSum+arr[i]); 
        maxSum = Math.max(maxSum, currentSum); 
    } 
    return maxSum; 
    } 
  
    /*main method */
    public static void main(String[] args) 
    { 
    int a[] = {-2, -3, 4, -1, -2, 1, 5, -3}; 
    int n = a.length;    
    int max_sum = maxSubArraySum(a, n); 
    System.out.println("Maximum sum is: "+ max_sum); 
    } 
} 

Output:

Maximum sum is: 7

This algorithm will find the max sum in O(n) time where n = size of the array.

Hope you guys understand the concept of kadens algorithm..

Happy Coding..!

Thanks for reading..!

Thank You..!