/****************************************************************************** * 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); } }