Educational Codeforces Round 63 (Rated for Div. 2) D. Beautiful Array

D. Beautiful Array

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

DP[i][0] : 과거에 x를 곱하지 않았고, 현재도 x를 곱하지 않는 부분합에 대한 DP

DP[i][1] : 과거에 x를 곱하거나 곱하지 않았고, 현재 x를 곱한 부분합에 대한 DP

DP[i][2] : 과거에 x를 곱했고, 현재 x를 곱하지 않는 부분합에 대한 DP

i를 쭉 탐색하면서, 가장 최댓값이 되는 부분합을 출력하자.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
ll x;
ll arr[300050], dp[300050][3];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> x;
    for (int i = 1; i <= n; i++) cin >> arr[i];
    ll maxv = 0;
    for (int i = 1; i <= n; i++) {
        dp[i][0] = max(dp[i - 1][0] + arr[i], arr[i]);
        dp[i][1] = max(max(dp[i - 1][0], dp[i - 1][1]) + arr[i] * x, arr[i] * x);
        dp[i][2] = max(dp[i - 1][1] + arr[i], dp[i - 1][2] + arr[i]);
        maxv = max(maxv, max(dp[i][0], max(dp[i][1], dp[i][2])));
    }
 
    cout << maxv;
 
    return 0;
}