思路与算法

Kadane维护当前结尾最大和及全部前缀最大子段和特征值；保存所有前人(分数+特征值)最大值作为新分数，128位保存真实大小后再取模。

正确性说明

Kadane的结尾转移覆盖以当前点结尾的全部非空段，结合此前特征最大值得到本前缀特征。新分数正好是已维护的前人分数加特征最大值；处理后将当前项纳入维护量，归纳得到全部真实分数及最大者。

复杂度

O(n)时间、O(1)额外状态空间，流式读入；128位足够n<=10^6和数值10^9的联合上界。

易错点

不得在参与大小比较前取模，真实最大分数可超过64位；最大值为负要保持符号，不能把初始最大和置0。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long p, x;
    cin >> n >> p >> x;
    long long ending = x, feature = x;
    __int128 score = x, best = 2 * (__int128)x, ans = x;
    for (int i = 1; i < n; i++) {
        cin >> x;
        ending = max(x, ending + x);
        feature = max(feature, ending);
        score = best;
        ans = max(ans, score);
        best = max(best, score + feature);
    }
    cout << (long long)(ans % p) << "\n";
}