CH1201:最大子序和题解

Solve this Problem with the Priority Queue

单调队列的主要目标其实跟单调栈的主要目标比较相似,都是在一个单调问题中,直接排除一些可以排除的答案进行运算

在本题中,我们会采用单调队列来解决。首先,我们采用前缀和来进行快速计算。然后,在前缀的前提下,我们会在本题中使用一个策略,那就是:如果有两个位置的前缀和\(sum[i]>sum[j],其中i<j\),那么处于\(i\)位置的元素对于我们来讲,是毫无用处的。原因是,如果我们要在\(m\)长度内获得和最大的子序列,对于一个这样前缀和又大、又靠前的元素,最优解绝不是由这个元素组成的。

我们来用几个代码块来简述我们的策略。

// ll stands for long long
const int maxn = 300200;
ll n, arr[maxn], sum[maxn], m, q[maxn];

声明了几个变量,not a big deal.

ll l = 1, r = 1, ans = -1e9;
q[1] = 0;
for (int i = 1; i <= n; i++)
{
    while (l <= r && q[l] < i - m)
        l++;
    ans = max(ans, sum[i] - sum[q[l]]);
    while (l <= r && sum[q[r]] >= sum[i])
        r--;
    q[++r] = i;
}

我们首先定义队头、队尾,还有一个无穷小的答案。之后,我们来枚举元素\(i\)。我们在循环中首先淘汰掉那些距离超过\(m\)的元素。之后我们来记录答案。然后就到我们实施策略的时候了。我们淘汰掉那些不属于最优解的答案。之后,我们记录在位置\(++r\)的答案为\(i\)。

完整代码:

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注