先预处理一下, 把 >8h 的变成 +1, <=8h 的变成 -1
现在问题就变成了: 找最长的连续一段使其和 >0
使用前缀和数组, 要求 i~j 的和, 公式是 sum[j] - sum[i - 1].
枚举左端点 i. 对于某个确定的 i, 要找以 i 为左端点的最长一段符合要求的区间, 即找满足条件 sum[j] > sum[i - 1] 的最大的 j
注意到 sum 数组的取值为 [-n, n], 故使用值域数组 values. value[k] 表示 sum[j] == k 的最大的 j. 该数组可以在求 sum 数组时一并求出.
满足条件 sum[j] > sum[i - 1] 的最大 j 即求 values[sum[i - 1] + 1], values[sum[i - 1] + 2], values[sum[i - 1] + 3], …, values[正无穷] 中的最大值.
此处可以使用类似于前缀和的做法, maxvalues[k] 表示 values 数组从 k + 1 到 正无穷 的最大值, 使用一遍从大到小的 for 循环可以求出.
利用 maxvalues[sum[i - 1] + 1] 即可求出上述要求的 j, 然后取所有 i 中最大的 j - i + 1 作为答案即可.