Kadane Algorithm

kadane.java

import java.io.*;
import java.lang.*;

class Test
{
    /*
    public static void main (String[] args) throws java.lang.Exception
    {
        int[] a = new int[]{-2, -3, 4, -1, -2, 1, 5, -3};
        int l = a.length;
        int max_current = a[0];
        int max_global  = a[0];
        for(int i = 1; i < l; i++ )
        {
            max_current = Math.max(a[i], (max_current + a[i]));
            if (max_current > max_global){
                max_global = max_current;    
            }
        }
        System.out.println(max_global);
    }
    */
    
    public static void main (String[] args) throws java.lang.Exception
    {
        int[] a = new int[]{4, 1, 1, -1, -3, -5, -6, 2, 6, -2};
        int l = a.length;
        int max_current = a[0];
        int max_global  = a[0];
        int start = 0;
        int s = 0;
        int e = 0;
        for(int i = 1; i < l; i++)
        {
            if (a[i] > (max_current + a[i])) {
                max_current = a[i];
                s = i;
            } else {
                max_current = max_current + a[i];
            }
            if (max_current > max_global) {
                start = s;
                e = i;
                max_global = max_current;
            }
        }

        System.out.println("max sum:      " + max_global);
        System.out.println("start index:  " + start);
        System.out.println("end   index:  " + e);
    }
}