Kadane’s Algorithm ( Largest Sum Contiguous Subarray )

Kadane's algoritm 

Kadane's algoritm is for finding the maxium sum of contiguous sub array of given array.

There is an array arr[] of size given n.

All the possible cotiguous subarray and their sum is manullay calculated in below picture.

    As you can see in the picture the max sum of cotiguous subarray is 8.

    For implementing the kadane's algorithm we have to follow below steps:

        1.    sum=0

        2.    max=Integer.MIN_VALUE

        3.    Loop for array ( for the every element)

               (a)    sum= sum+arr[i]

               (b)    max=Math.max(sum,max)

               (c)    if(sum<0)

                            {

                            sum=0

                            }  

        4.     return max

The code for kadane's algoritm is implemented below

public class kadane_maxSumSubArray {

    public static int kadane(int arr[]){

        int sum=0; //sum

        int max=Integer.MIN_VALUE; //Max sum

        for(int i=0;i<arr.length;i++){

            sum=sum+arr[i];

       

         max=Math.max(sum, max);

         if(sum<0){

            sum=0;

        }

    }

   

    }

public static void main(String[] args) {

    int arr[]={1, -2, 6, -1, 3};

   

System.out.println(kadane(arr));

}

}

 

Time complexity :  O(n)   {n is is the size of array}

Auxillary space : O(1)