（以下複雜度均不包含大數乘法運算）
網路上找到的解法大多是用 dp 以 O(n^2) 的方式 brute force 出來，但個人直覺想到的方法是先 greedy 的全部乘開，若是正數即回傳，做是負數便分別去掉左、右元素，遞迴取 max。而遇到 0 時，便在該處 split，遞迴取兩邊的 max。這樣的複雜度最差仍然是 O(n^2)，但大多數時候應該會比較快些，在 UVa 上的 Runtime 是 0.000。另外，因為乘積可能非常大，因此需要實作一部分的 BigInt 功能。
(Time complexity notations in the following analysis do not include the cost of multpling big integers.)
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 still has a worst case of O(n^2), but is usually faster, 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;
}