Overview

Flowers with different beauty values are planted in flower beds arranged in a row, but flowers cannot be planted in adjacent flower beds at the same time. The problem is to choose which flower beds to plant in so as to maximize the total beauty obtained.

Analysis

In this problem, due to the constraint that “flowers cannot be planted in adjacent flower beds at the same time,” we cannot plant flowers in every flower bed. A simple greedy approach of selecting in descending order of beauty does not yield the correct answer. For example, when the input is [2, 7, 9, 3, 1], if we select the largest value 9, we can no longer select the adjacent 7 and 3. However, the sum of 7 and 3 is greater than 9, so this is not optimal.

For optimization problems of this type where “a choice affects subsequent options,” dynamic programming (DP) is effective. The key observation is that depending on whether we selected or did not select the last flower bed we examined, the available choices for the next one change.

We define the DP table as follows: - \(dp[i]\) := the maximum beauty obtainable from the first \(i\) flower beds

The transitions are: - If we do not select the \(i\)-th flower bed: carry over the previous state \(dp[i-1]\) - If we select the \(i\)-th flower bed: we cannot select the \((i-1)\)-th, so it becomes \(dp[i-2] + A[i]\)

Therefore, the following recurrence holds: $\( dp[i] = \max(dp[i-1],\ dp[i-2] + A[i]) \)$

The initial conditions are: - \(dp[0] = A[0]\) - \(dp[1] = \max(A[0], A[1])\)

With these, the subsequent calculations proceed naturally.

Algorithm

Using dynamic programming, we update the maximum value for each flower bed considering both “selecting it” and “not selecting it.”

The specific steps are as follows: 1. Read the input and store it in array \(A\) 2. Prepare a DP array \(dp\) and set the initial values 3. Compute according to the recurrence \(dp[i] = \max(dp[i-1],\ dp[i-2] + A[i])\) 4. The final answer is stored in \(dp[N-1]\)

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

※ It is also possible to further reduce the space to \(O(1)\), but here we present the basic DP-based solution.

Implementation Notes

• Pay attention to array indices to avoid out-of-bounds access

• It is safe to add special handling for the case \(N=1\)

• Initialize the DP table correctly (especially the first two elements)

  Source Code

n = int(input())
a = list(map(int, input().split()))

if n == 1:
    print(a[0])
else:
    dp = [0] * n
    dp[0] = a[0]
    dp[1] = max(a[0], a[1])
    
    for i in range(2, n):
        dp[i] = max(dp[i-1], dp[i-2] + a[i])
    
    print(dp[n-1])

---

This editorial was generated by qwen3-coder-480b.