第2题-加速窗口收益

小红书9月17日机考题目与解析

推理集群上排着 $m$ 项作业，第 $p$ 项有一个收益 $v_p$（正数表示划算，负数表示亏本）。

调度允许开一次加速窗口：挑一段连续作业 $[L, R]$（$1 \le L \le R \le m$），把这段里每一项的收益改成原来的两倍。也可以一次都不开。

窗口用完之后（或者根本没用），再从作业序列里取出一段非空的连续作业，使它们的收益加起来尽量大。请给出这个最大和。

取出的那段至少要包含一项，不能交空段。

输入描述

首行给出正整数 $k$（$1 \le k \le 2 \times 10^1$），即询问组数。

随后 $k$ 行，每行先写出正整数 $m$（$1 \le m \le 2 \times 10^5$），再跟 $m$ 个整数 $v_1, v_2, \ldots, v_m$（$|v_p| \le 1000000000$），即该组作业条数和各项收益。

各组 $m$ 加起来不超过 $200000$。

输出描述

一行输出 $k$ 个整数，相邻两项用空格隔开，依次为每组询问的最大连续收益和。

样例 1

输入：

2
4 2 -3 4 -1
3 -5 -2 -7

输出：

8 -2

说明：

• 第一组：把 $[3,3]$（收益 $4$）翻倍，序列变成 $2, -3, 8, -1$。最大连续和是单独的 $8$。
• 第二组：全是负数，翻倍只会更亏，不开窗口，答案是最大的一项 $-2$。

样例 2

输入：

1
6 1 2 -5 3 -1 4

输出：

12

说明：把 $[4,6]$（$3, -1, 4$）翻倍，这段和从 $6$ 变成 $12$。左侧 $1, 2, -5$ 接上去会变差，所以最大就是 $12$。

思路

最大子段和变形。设最终取的答案段为 $S$、窗口为 $W$，总收益 $= \text{sum}(S) + \text{sum}(S \cap W)$；而 $S \cap W$ 本身也是数组的一段连续子段，其和不会超过全局最大子段和，因此上界是 $2 \times$ 最大子段和，并且把窗口恰好开在最大子段上就能取到。

• 若最大子段和 $\le 0$（所有元素为负）：翻倍只会更小，不开窗口，答案 = 最大元素；
• 否则：求最大子段和，答案 $= 2 \times$ 最大子段和。

两种写法等价：方法一是 Kadane 逐项转移；方法二用前缀和——最大子段和 $= \maxi(\text{pref}[i] - \min{j<i} \text{pref}[j])$。

代码

方法一：Kadane

t = int(input())
for _ in range(t):
    arr = list(map(int, input().split()))[1:]

    ans = max(arr)
    if ans <= 0:
        print(ans, end=' ')
        continue

    cur = arr[0]
    for x in arr[1:]:
        cur = max(x, cur + x)
        ans = max(ans, cur)
    print(ans * 2, end=' ')

方法二：前缀和

t = int(input())

def solve():
    a = list(map(int, input().split()))
    a = a[1:]

    pref = [0] * (len(a) + 1)
    for i in range(1, len(a) + 1):
        pref[i] = pref[i - 1] + a[i - 1]
    mx = max(a)
    mn = 0
    for i in range(1, len(pref)):
        mx = max(mx, pref[i] - mn)
        mn = min(mn, pref[i])
    mx = mx * 2 if mx >= 0 else mx
    print(mx, end=' ')

for _ in range(t):
    solve()