概要

「少なくとも 1 つ、連続する \(K\) 個をすべて選ぶ」という条件つきで、選んだ花壇の美しさの合計最大を求める問題です。

本質は、「本来なら選ばない負の値を、どの長さ \(K\) の区間なら最も少なくて済むか」を考えることです。

考察

まず、条件がなかったとします。
このときは当然、

• \(A_i > 0\) なら選ぶ
• \(A_i \le 0\) なら選ばない

のが最適です。

したがって、条件なしの最大値は

\[ \sum_{i=1}^{N} \max(A_i, 0) \]

です。

---

では、今回の条件
「どこか 1 か所、連続する \(K\) 個をすべて選ばなければならない」
を入れると何が起こるでしょうか。

ある区間 \([l, l+K-1]\) を「必ず全部選ぶ区間」にすると、

• その区間内の 正の値 は、もともと選ぶ予定だったので損しない
• その区間内の 負の値や 0 は、もともと選ばない予定だったのに、強制的に選ぶことになる

つまり、追加で損するのはその区間に含まれる 非正の値の総和 だけです。

---

ここで

• 正の値の合計を pos_sum
• 各 \(i\) について
  $\( \text{neg}_i = \begin{cases} A_i & (A_i \le 0) \\ 0 & (A_i > 0) \end{cases} \)$

とおくと、区間 \([l, l+K-1]\) を強制的に選ぶときの合計値は

\[ \text{pos\_sum} + \sum_{i=l}^{l+K-1} \text{neg}_i \]

になります。

よって、求める答えは

\[ \text{pos\_sum} + \max_{\text{長さ }K\text{ の区間}} \left( \text{neg の区間和} \right) \]

です。

---

なぜ素朴な方法ではだめか

例えば、

• すべての選び方を試す → \(2^N\) 通りで不可能
• すべての長さ \(K\) の区間を試し、そのたびに区間和を毎回計算する → \(O(NK)\) で、\(N=5 \times 10^5\) では間に合わない

そこで、長さ \(K\) の区間和を スライディングウィンドウ で管理すれば、全体を \(O(N)\) で処理できます。

---

具体例

例えば

\[ A = [4, -5, 3, -2, 6], \quad K=2 \]

とします。

まず、条件なしなら正の値だけ選んで

\[ 4+3+6=13 \]

です。

次に

\[ \text{neg} = [0, -5, 0, -2, 0] \]

となります。

長さ \(2\) の区間和は

• \([1,2]\): \(0 + (-5) = -5\)
• \([2,3]\): \(-5 + 0 = -5\)
• \([3,4]\): \(0 + (-2) = -2\)
• \([4,5]\): \(-2 + 0 = -2\)

最大は \(-2\) です。

したがって答えは

\[ 13 + (-2) = 11 \]

です。

アルゴリズム

1. 配列 \(A\) を見て、
   • \(A_i > 0\) なら pos_sum に加える
   • それ以外なら neg[i] = A_i
   • 正なら neg[i] = 0 とする。
2. neg 配列の長さ \(K\) の区間和の最大値を求める。
   • 最初の \(K\) 個の和を cur とする
   • 右に 1 つずつずらしながら $\( \text{cur} \leftarrow \text{cur} + \text{neg}[i] - \text{neg}[i-K] \)$ で更新する
   • その最大値を best とする
3. 答えは $\( \text{pos\_sum} + \text{best} \)$ を出力する。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• neg[i] には「強制的に選ぶことで追加される分」だけを入れます。
  つまり、正の値はすでに pos_sum に入っているので 0 にしておきます。

• 長さ \(K\) の区間和は、毎回最初から足し直すのではなく、スライディングウィンドウで更新すると \(O(N)\) で済みます。

• \(A_i\) の絶対値が大きいので、言語によっては 64bit 整数が必要です。Python ではそのままで問題ありません。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, K = data[0], data[1]
    A = data[2:]
    
    pos_sum = 0
    neg = [0] * N
    for i, x in enumerate(A):
        if x > 0:
            pos_sum += x
        else:
            neg[i] = x
    
    cur = sum(neg[:K])
    best = cur
    for i in range(K, N):
        cur += neg[i] - neg[i - K]
        if cur > best:
            best = cur
    
    print(pos_sum + best)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.4-high によって生成されました。