【題解】Codeforces 1155D. Beautiful Array

#include <iostream>
using namespace std;
 
const int maxn = 300005;
long long n, x, a;
long long dp[maxn][3], ans;
 
int main() {
    cin >> n >> x;
    for (int i = 1; i <= n; i++){
        cin >> a;
        //還沒開始乘x
        dp[i][0] = a + max(dp[i-1][0], 0LL);
        //處於乘x的subarray
        dp[i][1] = a*x + max(max(dp[i-1][0], dp[i-1][1]), 0LL);
        //已經做完乘x (離開subarray)
        dp[i][2] = a + max(max(dp[i-1][0], dp[i-1][1]), max(dp[i-1][2], 0LL));
        ans = max(max(ans, dp[i][0]), max(dp[i][1], dp[i][2]));
    }
    cout << ans << "\n";
}