思路
可以参考 1479. 最大子序列和
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1000010;
long long n,p;
long long a[N],s[N],f[N],t[N];
int main(){
cin>>n>>p;
long long maxn=-1e9;
t[0]=maxn;
s[0]=0;
for(long long i=1;i<=n;i++){
cin>>a[i];
s[i]=max(s[i-1]+a[i],a[i]); // s[i]的产生可以理解为a[1]到a[i-1]的积累能否被a[i]抵消
if(s[i]>maxn) maxn=s[i],t[i]=maxn; // t[i]即为特征值,从s[1]到s[i]中选最大的
else t[i]=t[i-1];
}
f[1]=t[1]%p; // 按题意给f[1]赋值
f[2]=(t[1]+f[1])%p; // 题目隐藏含义:无论如何f[2]都是第一个分数加上第一个特征值
long long res=-1e9;
for(long long i=3;i<=n;i++){
f[i]=max(f[i-1],f[i-1]+t[i-1]);
f[i]=f[i]%p;
}
if(f[1]>0) res=f[n];
else res=max(f[1],f[n]);
cout<<res%p;
return 0;
}
这个代码好像过不了吧
是的,只有我题解的代码可以过了(雾