概要

隣り合う花壇には同時に植えられないという制約のもとで、選んだ花壇の美しさの合計 \( \sum A_i \) を最大化する問題です。
「選ぶ／選ばない」を順に決める動的計画法（DP）で解きます。

考察

各花壇 \(i\) について「植える」か「植えない」かを決めたいですが、\(i\) に植えると \(i-1\) には植えられません。つまり、選択は直前の状態にだけ影響する“局所的な依存”になっています。

• 素朴な全探索：全ての部分集合を試すと \(2^N\) 通りで、\(N \le 2\times 10^5\) では到底間に合いません（TLE）。
• 貪欲法が難しい：例えば「大きい \(A_i\) から取る」などは、取ったせいで周りの選択肢が消えてしまい、全体最適を保証できません。
  例：\(A=[5,6,5]\) だと、真ん中の \(6\) を取ると合計 \(6\) ですが、両端を取れば \(5+5=10\) の方が良いです。

そこで、「先頭から見ていったときの最適値」をDPで持つと、矛盾なく最大値を計算できます。

アルゴリズム

\(dp[i]\) を「最初の \(i\) 個（\(1\)〜\(i\) 番目）の花壇だけを考えたときの最大合計美しさ」とします（\(dp[0]=0\)）。

\(i\) 番目を考えるとき、選択肢は2つです。

1. \(i\) 番目に植えない：その場合、最大値は前と同じで \(dp[i-1]\)
2. \(i\) 番目に植える：隣の \(i-1\) には植えられないので、\(dp[i-2] + A_i\)

よって遷移は次の通りです： - \(dp[i] = \max(dp[i-1],\ dp[i-2] + A_i)\)

このDPは配列で持つと \(O(N)\) メモリですが、必要なのは直前2つ（\(dp[i-1], dp[i-2]\)）だけなので、コードでは以下のように変数2つで更新しています。

• prev1：\(dp[i-1]\)
• prev2：\(dp[i-2]\)
• cur = max(prev1, prev2 + x)（ここで \(x=A_i\)）

最後に prev1 が \(dp[N]\) となり答えです。

具体例：\(A=[2,7,9,3]\) - \(i=1\): \(\max(0,0+2)=2\) - \(i=2\): \(\max(2,0+7)=7\) - \(i=3\): \(\max(7,2+9)=11\) - \(i=4\): \(\max(11,7+3)=11\) 答えは \(11\)（\(2+9\)）です。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)（DPを変数2つに圧縮）

実装のポイント

• \(A_i \le 10^9\)、\(N \le 2\times 10^5\) なので合計は最大で \(2\times 10^{14}\) 程度になります。Python の int は桁あふれしないのでそのままでOKです（他言語なら 64bit 整数が必要）。

• 入力が大きいので sys.stdin.readline を使うと安全です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    A = list(map(int, input().split()))
    
    prev2 = 0  # dp[i-2]
    prev1 = 0  # dp[i-1]
    for x in A:
        cur = max(prev1, prev2 + x)
        prev2, prev1 = prev1, cur
    
    print(prev1)

if __name__ == "__main__":
    main()

---

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