Kadane.java

import static java.util.concurrent.ThreadLocalRandom.current;

/**
 * A program finds the largest sum of contiguous subarrays.
 *
 * @see <a href="https://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane's_algorithm">Kadane's algorithm</a>
 */
class Kadane {

    static long kadane(final int[] A) {
        if (A == null) {
            throw new NullPointerException("A is null");
        }
        if (A.length == 0) {
            throw new IllegalArgumentException("A.length is zero");
        }
        long msf = A[0];
        long meh = A[0];
        System.out.printf("%1$4s %2$11s %3$11s %4$11s\n", "i", "A[i]", "meh", "msf");
        System.out.println("----------------------------------------");
        System.out.printf("%1$4d %2$11s %3$11d %4$11d\n", 0, A[0], meh, msf);
        for (int i = 1; i < A.length; i++) {
            meh = Math.max(meh, meh + A[i]);
            msf = Math.max(msf, meh);
            System.out.printf("%1$4d %2$11d %3$11d %4$11d\n", i, A[i], meh, msf);
        }
        System.out.println("----------------------------------------");
        return msf;
    }

    public static void main(final String... args) {
        final int[] A;
        if (args.length > 0) {
            A = new int[args.length];
            for (int i = 0; i < A.length; i++) {
                A[i] = Integer.parseInt(args[i]);
            }
        } else {
            A = new int[current().nextInt(0, 16)];
            for (int i = 0; i < A.length; i++) {
                A[i] = current().nextInt(-5, 5);
            }
        }
        System.out.printf("%1$40d\n", kadane(A));
    }

    /**
     * Creates a new instance.
     */
    private Kadane() {
        super();
    }
}