Tuesday, October 15, 2019

UVa 787 - Maximum Sub-sequence Product

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

No comments:

Post a Comment