Maximum Sub-sequence Product

Bob needs money, and since he knows you are here, he decided to gamble intelligently. The game is rather simple: each player gets a sequence of integers. The players must determine, by using their mega-pocket computers, which is the maximum product value which can be computed with non empty sub-sequences of consecutive numbers from the given sequence. The winner is the one which gets first the right result.

Can you help Bob with a program to compute quickly the wanted product, particularly when the sequence is quite long ?

Input 

The input file contains sequences of numbers. Each number will have at most 5 digits. There will be at most 100 numbers in each sequence. Each sequence starts on a new line and may continue on several subsequent lines. Each sequence ends with the number -999999 (which is not part of the sequence).

Output 

The maximum sub-sequence product for each sequence must be written on the standard output, on a different line. A simple example is illustrated in the sample below.

Sample Input 

1 2 3 -999999
-5 -2 2 -30 -999999
-8 -999999
-1 0 -2 -999999

Sample Output 

6
120
-8
0

---

做法 : O(N^2)
原本想做 O(N), 但是怕除法太耗時間, 因此改用 O(N^2)

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int[] A = new int[200];
		int n, i, j;
		while(input.hasNext()) {
			n = 0;
			while(input.hasNextInt()) {
				A[n] = input.nextInt();
				if(A[n] == -999999)
					break;
				n++;
			}
			BigInteger max = BigInteger.valueOf(A[0]);
			BigInteger tmp;
			for(i = 0; i < n; i++) {
				tmp = new BigInteger("1");
				for(j = i; j < n; j++) {
					tmp = tmp.multiply(BigInteger.valueOf(A[j]));
					max = tmp.max(max);
				}
			}
			System.out.println(max);
		}
	}
}