// UVa 787 - Maximum Sub-sequence Product
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
private static BigInteger maxProduct;
private static final BigInteger NEGATIVE_INFINITY = BigInteger.valueOf(1000000).pow(100).multiply(BigInteger.valueOf(-1));
private static void consider(BigInteger product) {
if (product.compareTo(maxProduct) > 0)
maxProduct = product;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNextInt()) {
maxProduct = NEGATIVE_INFINITY;
BigInteger productFromStart = BigInteger.ONE;
BigInteger productAfterFirstNeg = NEGATIVE_INFINITY; // productAfterFirstNeg will be -oo if there are no negatives so far
for (int i = scanner.nextInt(); i != -999999; i = scanner.nextInt()) {
if (i == 0) {
consider(BigInteger.ZERO);
productFromStart = BigInteger.ONE;
productAfterFirstNeg = NEGATIVE_INFINITY;
} else if (i > 0) {
productFromStart = productFromStart.multiply(BigInteger.valueOf(i));
consider(productFromStart);
if (productAfterFirstNeg.compareTo(NEGATIVE_INFINITY) != 0) {
productAfterFirstNeg = productAfterFirstNeg.multiply(BigInteger.valueOf(i));
consider(productAfterFirstNeg);
}
} else {
productFromStart = productFromStart.multiply(BigInteger.valueOf(i));
consider(productFromStart);
if (productAfterFirstNeg.compareTo(NEGATIVE_INFINITY) != 0) {
consider(productAfterFirstNeg);
productAfterFirstNeg = productAfterFirstNeg.multiply(BigInteger.valueOf(i));
consider(productAfterFirstNeg);
} else {
productAfterFirstNeg = BigInteger.ONE;
}
}
}
System.out.println(maxProduct);
}
}
}
Tuesday, October 15, 2019
UVa 787 - Maximum Sub-sequence Product
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment