题解：P11642 【MX-X8-T1】「TAOI-3」幸运草

先把话放在前头：如果你全错，请查看你有没有开 long long！

思路

本题的关键问题在于确定替换哪个子区间（如果有的话）可以最大化总和。

考虑每个元素替换后的增益，即 $x$ 与当前元素的差值。我们需要找到一个子序列，使得这个子序列的增益总和最大。这个最大增益如果是正数则替换，否则为负数将不进行替换。

我们可以使用复杂度为 $O(n)$ 的 $\text{Kadane}$ 算法来解决这个问题。

注意这道题因为 $10^9 + 10^9$ 会超出 int 所以要开 long long，在进行比较时可以使用 0ll 作为 long long 类型的数字 $0$。

代码

这里使用 $tmp$ 维护当前子数组的最大增益，$ans$ 记录全局最大增益。

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
long long n, x, sum, tmp, ans, a[100005];
int main()
{
    cin >> n >> x;
    for (long long i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    tmp = x - a[1];
    ans = tmp;
    for (long long i = 2; i <= n; i++)
    {
        tmp = max(x - a[i], tmp + x - a[i]);
        ans = max(ans, tmp);
    }
    cout << sum + max(0ll, ans) << endl;
    return 0;
}