Codeforces 1155 D Beautiful Array DP，最大子段和

题意

给出一个长度为(n)的数列和数字(x),经过最多一次操作将数列的一个子段的每个元素变为(a[i]*x),使该数列的最大子段和最大

分析

将这个数列分为3段考虑，第一段和第三段是未修改的，第二段是修改的子段

设(dp[i][j])为第(i)个数字为第(j+1)段的最大子段和

三种转移方程

• 第一段：(dp[i][0]=max(a[i],dp[i-1][0]+a[i]))
• 第二段：(dp[i][1]=max(a[i]*x,dp[i-1][0]+a[i]*x,dp[i-1][1]+a[i]*x))
• 第三段：(dp[i][2]=max(a[i],dp[i-1][0]+a[i],dp[i-1][1]+a[i],dp[i-1][2]+a[i]))

Code

    #include<bits/stdc++.h>
    #define fi first
    #define se second
    using namespace std;
    typedef long long ll;
    const double PI=acos(-1.0);
    const double eps=1e-6;
    const ll inf=1e18;
    const ll mod=1e9+7;
    const int maxn=3e5+10;
    int n;
    ll x;
    ll a[maxn];
    ll dp[maxn][3];
    int main(){
        ios::sync_with_stdio(false);
        cin>>n>>x;
        ll ans=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            dp[i][0]=max(a[i],dp[i-1][0]+a[i]);
            dp[i][1]=max({a[i]*x,dp[i-1][1]+a[i]*x,dp[i-1][0]+a[i]*x});
            dp[i][2]=max({a[i],dp[i-1][0]+a[i],dp[i-1][1]+a[i],dp[i-1][2]+a[i]});
            ans=max({ans,dp[i][2],dp[i][0],dp[i][1]});
        }
        cout<<ans<<endl;
        return 0;
    }