D. Beautiful Array DP

https://codeforces.com/contest/1155/problem/D

这个题目还是不会写，挺难的，最后还是lj大佬教我的。

这个题目就是要分成三段来考虑，

第一段就是不进行乘，就是直接求这一个区间的最大的一段区间的最大值。

第二段就是后面有一部分进行乘法，前面有一部不进行乘法。这个也同样求一个区间的最大值。

第三段就是前面有一部分和后面有一部分不进行乘法，中间有一部分进行乘法，同样求这个区间的最大值。

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<queue>

#include<vector>

#define inf 0x3f3f3f3f

#define debug(x) cout<<"-----"<<" x = "<<x<<"-----"<<endl

using namespace std;

typedef long long ll;

const int maxn = 3e5 + ;

ll dp1[maxn], dp2[maxn], dp3[maxn];

ll a[maxn];

ll max_(ll x,ll y,ll z)

{

    ll ans = max(x, y);

    return max(ans, z);

}

int main()

{

    int n, k;

    ll ans = ;

    scanf("%d%d", &n, &k);

    for (int i = ; i <= n; i++) scanf("%lld", &a[i]);

    for (int i = ; i <= n; i++)

    {

        dp1[i] = a[i] + max(1ll * , dp1[i - ]);

        ans = max(ans,dp1[i]);

    }

    for (int i = ; i <= n; i++)

    {

        dp2[i] = a[i] * k + max_(dp1[i - ], dp2[i - ],);

        ans = max(dp2[i], ans);

    }

    dp3[] = dp2[] + a[];

    ans = max(ans, dp3[]);

    for (int i = ; i <= n; i++)

    {

        dp3[i] = a[i] + max_(dp2[i - ], dp3[i - ],);

        ans = max(ans, dp3[i]);

    }

    printf("%lld\n", ans);

    return ;

}