D. Yet Another Yet Another Task

https://codeforces.com/contest/1359/problem/D

这题不看editorial也是做不出来的。讨论区里面说这题其实还有比较老实的办法完成，不过我也没有仔细看这些实现方式，好像还蛮复杂的。

这题目有两个关键点：

  1. 枚举可能的最大值，因为最大值就是[0,30]，所以时间复杂度没啥问题。
  2. 在满足最大值区间的情况下计算区间和的最大值。

editorial里面的思路是，如果某个值大于mx的话，那么可以使用替代值-inf. 所以最终代码是 

def run(arr):
    ans = 0
    inf = 10 ** 9
    for mx in range(0, 31):
        cur = 0
        best = 0
        for x in arr:
            cur += -inf if x > mx else x
            best = min(cur, best)
            ans = max(ans, (cur - best) - mx)
    return ans

我看到这个提交也比较有意思 https://codeforces.com/contest/1359/submission/82315324. 它并没有将大于mx的值设置成为-inf. 而是只使用<=mx的值。计算最大子序列之和是个经典的问题，在这个问题的基础上扩展下，当遇到>mx的话那么认为序列到此结束了。我觉得下面这个解法可能更好理解。 

def run(arr):
    ans = 0
    for mx in range(0, 31):
        acc = 0
        for x in arr:
            if x > mx:
                acc = 0
                continue
            acc += x
            acc = max(acc, 0)
            ans = max(ans, acc - mx)
    return ans