Kadane’s Algorithm

 

public class kadane {
    public static void main(String args[])
    {
            System.out.println("Kadane Algorithm");
           
            int A[]={-2, -3, 4, -1, -2, 1, 5, -3};
            int max , max_final , i;
            max=max_final=0;
            int size=A.length;
            for(i=0;i<size;i++)
            {
                max=max+A[i];
                if(max < 0)
                    max=0;
               
                if(max_final<max)
                    max_final=max;
                           
            }
            System.out.println("Maximum sum : "+max_final);
    }
}

Output:

Maximum sum : 7