AGC 008 B - Contiguous Repainting

B - Contiguous Repainting

概略

N個のマスが横に並んでいて、整数aiが書かれている。

以下の操作を好きなだけ行う

・連続するK個のマスを全て白く塗るか、黒く塗る。

黒いマスの合計を最大化したい制約
・1 <= N <= 10^5
・1 <= K <= N
・ |ai| <= 10 ^ 9

解法
000000000
111100000
111000000
111001111
111000001
111111101
110000101
のように書いてみると、連続したK個以外のマスは好きな色で塗れる事に気づく。
なぜなら色を重ねる時に、K個ずつ塗るので、どこかしらK個は自由に塗れない。

類題
D - Static Sushi

public static void main(String[] args)
    {
        N =sc.nextInt();
        K = sc.nextInt();
        a = sc.nextLongArray(N);
        long[] lSumMax = new long[N + 1];
        long[] rSumMax = new long[N + 1];
        long[] rui = new long[N+1];

        for (int i = 1; i < N+1; i++)
            rui[i] = rui[i-1]+a[i-1];


        for (int i = 1; i < N+1; i++)
        {
            lSumMax[i] = Math.max(lSumMax[i-1],lSumMax[i-1]+a[i-1]);
        }
        for (int i = 1; i < N+1; i++)
        {
            rSumMax[i] = Math.max(rSumMax[i - 1], rSumMax[i - 1] + a[N - i]);
        }

        long best=0;
        for (int l = 0; l <= N-K ; l++)
        {
            long score = 0;
            int r = N-K-l;
            score += lSumMax[l];
            score += rSumMax[r];

            long bonus = rui[N-r] - rui[l];//todo
            score += bonus < 0 ? 0 : bonus ;

            best = Math.max(best, score);
        }
        System.out.println(best);
    }