Cubic.java

Below is the syntax highlighted version of Cubic.java from §4.1 Performance.

/******************************************************************************
 *  Compilation:  javac Cubic.java
 *  Execution:    java Cubic n < input.txt
 *
 *  A program with cubic running time. Read in n long integers
 *  and find the triple whose sum is closest to 0.
 *
 *  Limitations
 *  -----------
 *     - we assume no sum of three integers will overflow a long
 *
 ******************************************************************************/

public class Cubic {

    public static void main(String[] args) {

        // read in input data
        long[] a = StdIn.readAllLongs();
        int n = a.length;

        // find triple whose sum is closest to 0
        long best = Long.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                for (int k = j+1; k < n; k++) {
                    long sum = a[i] + a[j] + a[k];
                    if (Math.abs(sum) < Math.abs(best)) best = sum;
                }
            }
        }

        StdOut.println(best);
    }

}