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..!



Categories: HackerRank Questions, Interview, JAVA, Uncategorized

Tags: , , , , , , , , , , , ,

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: