https://leetcode.com/problems/longest-well-performing-interval/discuss/334897/tiankonguse
比赛145题解： 1122 Relative Sort Array 1123 Lowest Common Ancestor of Deepest Leaves 1124 Longest Well-Performing Interval 1125 Smallest Sufficient Team
题意：一天工作大于8小时算是工作量饱和。 如果在连续若干天内，工作量饱和的天数大于不饱和天数，则这个天数成为工作良好天数。 求最大的工作良好天数。
思路：问题可以转化一下，工作饱和标记为1，不饱和标记为-1，问题则是求区间和大于 0 的最长区间。 这道题显然需要依次求出i为区间结尾时的最优答案，最终答案则是所有答案里面的最大值。
如果使用O(n^2)暴力求所有区间和的话。 由于数据范围是 10000，在 ACM 中这个做法肯定会超时的， 在 OI 中，这个只能得 30 分的。
我们可以分析数据，假设当前位置i的前缀和是sum[i]。 如果sum[i]>0，那显然整个前缀都是答案。
如果sum[i]<=0，那我们需要找到一个区间sum[j,i]，使得sum[j,i]>0。 因为sum[0,j-1] + sum[j,i] = sum[i]，带入到sum[j,i]中，即可得到sum[i] - sum[0,j-1] > 0。 公式转化一下，即可得到0 >= sum[i] > sum[0,j-1]。
由此，就可以发现，我们的目标是找到最前面的比sum[i]小的位置，从而就可以计算出i的最优答案。 怎么找到这个最优值呢，我甚至想到了树套树，第一层树找到前面所有小于sum[i]的位置集合，第二层树找到这个集合里的最小值。
当然，这个其实有更简单的方式，只是不容易想到而已。
由于整个序列是有1和-1组成，所以前缀和组成的序列是严格连续的。 严格连续的定义指的是相邻的两个前缀和之差肯定是1。
假设最优答案是k，即sum[k] < sum[i] <= 0。 那么在sum[k]肯定是sum[i]-1。
反证法：假设最优答案sum[k] < sum[i]-1，不妨假设位置是L，值sum[L] < sum[i]-1。 由于前缀和的严格连续性，从起始位置到位置L之间肯定存在-1, -2, ..., sum[i]-1, ..., sum[L]的前缀和。 这样，在位置L之前肯定存在另一个位置，值是sum[i]-1，比位置L更优。 假设不成立。
所以，最优答案是sum[i]-1。
PS：对于反正法的题目，其实不是好题目。 因为这个算法算是启发式的算法，面试上不能在这道题上做太多的延伸和扩展。 其实使用逻辑推理也能得到启发式算法，但是这个就需要很强大的分析问题能力了。