K-Concatenation [CodeChef January Challenge 2018 C]

https://www.codechef.com/JAN18/problems/KCON

N要素の配列Aがある。
これをK個繋げたNK要素の配列をBとする。
配列Bの連続部分列の中での総和の最大値は？

解法

最大化できる区間を場合分けして全部考えてみる

• 配列Aの中の区間の最大値
• 配列A全体の総和が正になる場合は、最初の配列Aの最大接尾と内側の全てと最後の配列Aの最後接頭
• 配列A全体の総和が負になる場合は、配列Aの最大接尾と配列Aの最後接頭

これをやれば良さそう。
K=1の時は後半二つは出来ないので注意。
　
そのため「1.区間最大値 2.最大接頭 3.最大接尾」を頑張って求めよう。
最大接頭と最大接尾は累積和を使って最大値を求める。
区間最大値は累積和と今までの累積和の最小を使って求めることができる。
こういう風にやる
　
コーナーケースとして全ての数が0以下の場合がある。
この場合は配列Aの最大値が答えとなるので別途処理しておこう。
これをやっておかないと最大接頭+最大接尾を答えとしたい時に、範囲が無い答えが出てきてしまうためである。

typedef long long ll;
#define INF 1LL<<60
int N, K; ll A[101010];
ll B[101010];
//---------------------------------------------------------------------------------------------------
void solve() {
    cin >> N >> K;
    rep(i, 0, N) cin >> A[i];

    ll ma = -INF;
    rep(i, 0, N) ma = max(ma, A[i]);
    if (ma <= 0) {
        printf("%lld\n", ma);
        return;
    }

    B[0] = A[0];
    rep(i, 1, N) B[i] = B[i - 1] + A[i];

    // range max
    ll rmax = -INF;
    ll mi = 0;
    rep(i, 0, N) {
        rmax = max(rmax, B[i] - mi);
        mi = min(mi, B[i]);
    }

    // post max
    ll posmax = B[N - 1];
    rep(i, 0, N) posmax = max(posmax, B[N - 1] - B[i]);

    // pre max
    ll premax = 0;
    rep(i, 0, N) premax = max(premax, B[i]);

    ll sm = B[N - 1];

    ll ans = rmax;
    if (2 <= K) {
        ans = max(ans, premax + posmax);
        if (0 < sm) ans = max(ans, premax + posmax + sm * (K - 2));
    }

    printf("%lld\n", ans);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) solve();
}