Overview

This is a problem of maximizing the total beauty \(\sum A_i\) of selected flower beds, under the constraint that adjacent flower beds cannot be selected simultaneously. We solve it using dynamic programming (DP) that sequentially decides “select / don’t select” for each flower bed.

Analysis

For each flower bed \(i\), we want to decide whether to “plant” or “not plant,” but if we plant at \(i\), we cannot plant at \(i-1\). In other words, the choice has a “local dependency” that only affects the immediately preceding state.

• Naive exhaustive search: Trying all subsets gives \(2^N\) possibilities, which is far too slow for \(N \le 2\times 10^5\) (TLE).
• Greedy is difficult: For example, strategies like “take the largest \(A_i\) first” don’t work because taking one element eliminates neighboring choices, making it impossible to guarantee global optimality. Example: For \(A=[5,6,5]\), taking the middle value \(6\) gives a total of \(6\), but taking both ends gives \(5+5=10\), which is better.

Therefore, by maintaining “the optimal value when looking from the beginning” using DP, we can correctly compute the maximum value without contradictions.

Algorithm

Let \(dp[i]\) be “the maximum total beauty considering only the first \(i\) flower beds (from the \(1\)st to the \(i\)th)” (with \(dp[0]=0\)).

When considering the \(i\)th flower bed, there are two choices:

1. Don’t plant at the \(i\)th: In this case, the maximum value stays the same as before: \(dp[i-1]\)
2. Plant at the \(i\)th: We cannot plant at the adjacent \(i-1\), so the value is \(dp[i-2] + A_i\)

Therefore, the transition is as follows: - \(dp[i] = \max(dp[i-1],\ dp[i-2] + A_i)\)

Storing this DP in an array requires \(O(N)\) memory, but since we only need the last two values (\(dp[i-1], dp[i-2]\)), the code updates using just two variables as follows:

• prev1: \(dp[i-1]\)
• prev2: \(dp[i-2]\)
• cur = max(prev1, prev2 + x) (where \(x=A_i\))

At the end, prev1 equals \(dp[N]\), which is the answer.

Concrete example: \(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\) The answer is \(11\) (which is \(2+9\)).

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (DP compressed to two variables)

Implementation Notes

• Since \(A_i \le 10^9\) and \(N \le 2\times 10^5\), the total can be up to approximately \(2\times 10^{14}\). Python’s int does not overflow, so it works as-is (in other languages, 64-bit integers are required).

• Since the input can be large, using sys.stdin.readline is recommended for safety.

  Source Code

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()

---

This editorial was generated by gpt-5.2-high.