網路上找到的解法大多是用 dp 以 O(n^2) 的方式 brute force 出來,但個人直覺想到的方法是先 greedy 的全部乘開,若是正數即回傳,做是負數便分別去掉左、右元素,遞迴取 max。而遇到 0 時,便在該處 split,遞迴取兩邊的 max。這樣的複雜度因測資內容而異,但大多數時候應該會比 O(n^2) 快些,在 UVa 上的 Runtime 是 0.000。另外,因為乘積可能非常大,因此需要實作一部分的 BigInt 功能。
A lot of the solutions found on the Internet uses dynamic programming and brute forces the results in O(n^2). However, the first way that came into mind is to greedily get the product of all the elements. If the product is negative, we remove the leftmost and rightmost element respectively and recursively get the maximum value. If 0 is encountered, split the array, and recursively get the maximum of the two sides. The time complexity of this algorithm differs with the input, but is usually faster than O(n^2), resulting in a runtime of 0.000 on UVa.

UVa Link

#include <cstdio>

const int SIZE = 100, BASE = 100000;
int in[SIZE];

struct Product {
    int sign = 0; // 0 for positive, 1 for negative
    long long data[SIZE] = { 0 }; // Int overflows!
    // Calculate the product of in[start] to in[end-1]
    void mult(int in[], int start, int end) {
        if (in[start] < 0) {
            data[0] = -in[start];
            sign = 1 - sign;
        } else data[0] = in[start];
        for (int i = start + 1; i < end; i++) {
            int carry = 0, multiplier;
            if (in[i] < 0) {
                multiplier = -in[i];
                sign = 1 - sign;
            } else multiplier = in[i];
            for (int j = 0; j < SIZE; j++) {
                data[j] *= multiplier;
                data[j] += carry;
                carry = data[j] / BASE;
                data[j] %= BASE;
            }
        }
    }
    // 1 if this > y, 0 if this == y, -1 if this < y
    int cmp(Product y) {
        if (sign == 0 && y.sign == 1) return 1;
        if (sign == 1 && y.sign == 0) return -1;
        int flip = sign ? -1 : 1;
        for (int i = SIZE - 1; i >= 0; i--) {
            if (data[i] == 0 && y.data[i] != 0) return -1 * flip;
            if (data[i] != 0 && y.data[i] == 0) return 1 * flip;
            if (data[i] != 0 && y.data[i] != 0) {
                if (data[i] == y.data[i]) continue;
                else return (data[i] > y.data[i]) ? 1 * flip : -1 * flip;
            }
        }
        return 0;
    }
    void prnt() {
        if (sign) printf("-");
        int i;
        for (i = SIZE - 1; i >= 0 && data[i] == 0; i--);
        if (i == -1) printf("%d\n", 0);
        else {
            printf("%lld", data[i--]);
            for (int j = i; j >= 0; j--) printf("%05lld", data[j]);
            printf("\n");
        }
    }
    int isZero() {
        int res = 1;
        for (int i = 0; i < SIZE; i++) {
            if (data[i] != 0) {
                res = 0;
                break;
            }
        }
        return res;
    }
} zero;

Product solve(int in[], int start, int end) {
    int newStart, newEnd;
    for (newStart = start; newStart < end && in[newStart] == 0; newStart++);
    for (newEnd = end; newEnd > newStart && in[newEnd-1] == 0; newEnd--);
    if (newStart != start || newEnd != end) {
        Product q = solve(in, newStart, newEnd);
        return (q.cmp(zero) == 1) ? q : zero;
    } // Remove 0 at the beginning and end to avoid too much recursion
    Product p;
    if (start == end) return p;
    p.mult(in, start, end);
    if (start + 1 == end) return p;
    if (p.sign == 1) {
        Product q = solve(in, start + 1, end), r = solve(in, start, end - 1);
        return (q.cmp(r) == 1) ? q : r;
    } else if (p.isZero() == 1) {
        int i;
        for (i = start; i < end && in[i] != 0; i++);
        Product q = solve(in, start, i), r = solve(in, i + 1, end);
        if (q.sign == 1 && r.sign == 1) return zero;
        else return (q.cmp(r) == 1) ? q : r;
    } else return p;
}

int main() {
    int tmpIn;
    while (scanf("%d", &tmpIn) != EOF) {
        int n = 0;
        in[n++] = tmpIn;
        while (1) {
            scanf("%d", &tmpIn);
            if (tmpIn == -999999) break;
            else in[n++] = tmpIn;
        }
        Product p = solve(in, 0, n);
        p.prnt();
    }
    return 0;
}