本题的突破口是数据范围n=1e4.这是一个比较奇怪的数字。通常来说如果允许nlogn的复杂度，那么n可以达到1e5；类似的，如果是n^2的复杂度，那么n大概就是1000. 在这里，很可能是一个大概是存在100的常数k，使得复杂度的限制在o(kn)。于是我们大概可以猜到，这个k就是跟26或者26^2相关，也就是英文字母的个数。
于是我们就想到了穷举本题中的最大频次字符x和最小频次字母y。这样的话，我们需要在原字符串里面找一个滑窗，使得x的频次与y的频次之差最大，而其他字母都没有任何作用。这就联想到，如果将x的字符都替换为1，y的字符都替换为-1，其他字符都替换为0，那么不就是变成了寻找max subarray sum的题目了吗？
但是注意，这里有一点不同，根据题意，我们想要找的subarray必须至少包含一个-1. 传统的kadane算法，我们很有可能找出只有+1的subarray。不过解决方法和kadane的思想差不多。
我们依然按照kadane算法的思路，但是设置两个临时变量：curSum0表示以当前元素为结尾、不包含-1的最大subarray sum，另外用curSum1表示以当前元素为结尾、已经包含-1的最大subarray sum。转移方程如下：
for (int i = 0; i < n; i++)
{
if (nums[i] == 1)
{
curSum1 = curSum1+nums[i];
curSum0 = max(curSum0+nums[i], nums[i]);
}
else if (nums[i] == -1)
{
curSum1 = max(nums[i], max(curSum0, curSum1)+nums[i]); // 三种情况可以转移到新的curSum1
curSum0 = 0; // 因为nums[i]是-1，curSum0没有意义，只能置零
}
ret = max(ret, curSum1);
}特别注意，curSum0的初始值可以是0，但是curSum1的初始值必须设置为INT_MIN.
这样，总的时间复杂度是o(676n).
我们发现在上面的表达式里，当nums[i]不是1也不是-1的时候，curSum0和curSum1都没有更新，循环是空跑的。所以我们其实只需要关心那些nums[i]非0的位置。
我们提前将所有是+1的位置放在数组pos0里，所有是-1的位置放在数组pos1里，分别用指针i和j来定位这两个数组元素。每次我们比较pos0[i]和pos1[j]哪个更小，前者更小的话，我们就知道pos0[i]这个位置上有一个+1，按照之前的第一个分支去更新curSum0和curSum1，然后自增i. 反之后面更小的话，我们就知道pos1[j]这个位置上有一个-1，就按照之前的第一个分支去更新curSum0和curSum1，别忘了自增j。
注意i和j可能会有其中某一个先走到尽头。如果其中一个走到尽头，那么我们必然移动另一个指针。
这样的时间复杂度是多少？看上去仍然是是o(676n)，但事实上，我们每固定了一个最大频次的字符a，其他所有字符都被看做为最小频次的字符，且只访问了一次。所以时间复杂度优化到了o(26n).
补充： 有网友问，我感觉第二种做法不是严格的O(26 * N). https://youtu.be/P6KnO-Dw0Fo?t=2204 即使可以认为b的pos1循环遍26次就是O(N) (e.g. 小x, 小y), 但是a的pos0在内层循环也遍历了26次而不是一次. 所以两者加一起肯定大于o(N)但是小于O(26N)
答：应该这么理解：当第一个for循环是字母a，那么照你的说法，字母a的所有位置都走了26次，外加其他所有位置都走了一次。当第一个for循环是字母b，同理，字母b的所有位置都走了26次，外加其他所有位置都走了一次。以此类推。把第一个for循环都搞完后，那么每个字母的位置都走了重复26次，外加所有的位置都走了26次。总开销不依然是26N吗？