CF1660D Maximum Product Strikes Back

给定一个包含 $n$ 个整数的数组 $a$。对于每个 $i$（$1 \le i \le n$），都有不等式 $-2 \le a_i \le 2$ 成立。 你可以从数组的开头删除任意数量（可能为 $0$）的元素，也可以从数组的末尾删除任意数量（可能为 $0$）的元素。你也可以删除整个数组。 你需要回答：应从数组开头删除多少个元素，从数组末尾删除多少个元素，使得剩下数组中元素的乘积最大。如果有多种方法可以得到最大乘积的数组，你可以输出其中任意一种。 空数组（长度为 $0$ 的数组）的元素乘积视为 $1$。

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示数组 $a$ 的长度。 下一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$|a_i| \le 2$），表示数组 $a$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出两个非负整数 $x$ 和 $y$（$0 \le x + y \le n$），表示从开头删除 $x$ 个元素，从末尾删除 $y$ 个元素，使得剩下数组中元素的乘积最大。 如果有多种方法可以得到最大乘积，可以输出其中任意一种。空数组的元素乘积视为 $1$。

在第一个样例中，最大乘积为 $2$。因此，你可以删除前三个元素（得到数组 $[2]$），或者删除最后两个和第一个元素（同样得到数组 $[2]$），或者删除最后两个元素（得到数组 $[1, 2]$）。所以本例的答案可以是：“3 0”，或“1 2”，或“0 2”。 在第二个样例中，最大乘积为 $1$。你可以删除所有元素，因为空数组的乘积为 $1$。因此答案是“3 0”，但也有其他可能的答案。 在第三个样例中，你可以删除数组的前两个元素，得到数组 $[-2, 2, -1]$。此时元素乘积为 $(-2) \times 2 \times (-1) = 4$。这是可以得到的最大值。因此本例的答案是：“2 0”。 由 ChatGPT 4.1 翻译