B - Neutralize SoundHound Programming Contest 2018

B: Neutralize - SoundHound Programming Contest 2018 Masters Tournament 本戦 (Open) | AtCoder

問題概略　
要素Nの数列がある。連続したK個を0にする操作を何回か繰り返し、総和を最大化したい。

制約
1≤K≤N≤2×10^5
−10^9≤bi≤10^9
入力中の値はすべて整数である。

解法
解けなかったなあああっぁあぁぁああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああ
くやしいなあかｓっかあああああああああ

連続したK個を0にするということは、同じ区間で何回も操作をする意味はないので、ある右端について、操作は一回しか行われない。
また、K個を0にする操作はK個以上を0にする操作と言い換えられる。
ていうかこれ、ここまでの最大値は〇〇で～って感じで出来て、それを元に次の値を考えられますね。つまりdpで出来ますね
先頭から見ていき、dp[i]にはi個までへの操作で最大の総和をもたせる。
dp[i]にはdp[i-1]に薬品の値を足した物か、左のK個以上を0にした時の最大の値を代入する。
後者はdp[i-k] ~dp[0]を探索すれば求められるが、無理　遅い
実はmax[i]にdp[0 ~ i]の最大値を代入するようにすれば、O(1)で求まる。
線形時間

類題
蟻本p139 Face the Righ way(POJ No.3276)

 public static void main(String[] args)
    {
        //longを忘れるなオーバーフローするぞ
        N = sc.nextInt();
        K = sc.nextInt();
        A = sc.nextIntArray(N);
        long[] dp = new long[N + 1];
        long[] max = new long[N + 1];
        for (int i = 1; i < N + 1; i++)
        {
            if (i - K >= 0)
            {
                dp[i] = Math.max(dp[i - 1] + A[i - 1], max[i - K]);
            }
            else
            {
                dp[i] += dp[i - 1] + A[i - 1];
            }
            max[i] = Math.max(max[i - 1], dp[i]);
        }
        System.out.println(dp[N]);
    }