CF1750B Maximum Substring

一个二进制字符串是只包含字符 $0$ 和 $1$ 的字符串。给定一个二进制字符串 $s$。 对于 $s$ 的某个非空子串 $^\dagger$ $t$，其中包含 $x$ 个字符 $0$ 和 $y$ 个字符 $1$，其代价定义如下： - 若 $x>0$ 且 $y>0$，则代价为 $x \cdot y$； - 若 $x>0$ 且 $y=0$，则代价为 $x^2$； - 若 $x=0$ 且 $y>0$，则代价为 $y^2$。 给定长度为 $n$ 的二进制字符串 $s$，请你求出所有非空子串中的最大代价。 $^\dagger$ 字符串 $a$ 是字符串 $b$ 的子串，当且仅当 $a$ 可以通过删除 $b$ 最开头和最末尾的若干（可能为 $0$ 或全部）字符得到。

输入包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例个数。接下来是各个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示字符串 $s$ 的长度。 每个测试用例的第二行包含一个二进制字符串 $s$，其长度为 $n$。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一行一个整数，表示所有子串中的最大代价。

在第一个测试用例中，可以选择子串 $111$。它包含 $3$ 个字符 $1$ 和 $0$ 个字符 $0$，所以 $a=3$，$b=0$，代价为 $3^2=9$。 在第二个测试用例中，可以选择整个字符串。它包含 $4$ 个字符 $1$ 和 $3$ 个字符 $0$，所以 $a=4$，$b=3$，代价为 $4 \cdot 3=12$。 在第三个测试用例中，可以选择子串 $1111$，其代价为 $4^2=16$。 在第四个测试用例中，可以选择整个字符串，代价为 $4 \cdot 3=12$。 在第五个测试用例中，可以选择子串 $000$，其代价为 $3 \cdot 3=9$。 在第六个测试用例中，只能选择子串 $0$，其代价为 $1 \cdot 1=1$。 由 ChatGPT 5 翻译