Overview

This problem asks us to maximize the total beauty under the constraint that we cannot plant flowers in adjacent flower beds simultaneously. It can be efficiently solved using dynamic programming (DP).

Analysis

The Essence of the Problem

This problem is a maximum sum problem with the constraint that “adjacent elements cannot be selected simultaneously.” This is a typical problem pattern that can be solved with DP.

Issues with the Naive Approach

If we consider 2 choices (“plant” / “don’t plant”) for each flower bed, we would need to examine \(2^N\) combinations. Since \(N\) can be up to \(2 \times 10^5\), this approach is too slow (TLE).

Key Insight

When making a decision for each flower bed, the only thing that matters is whether we planted a flower in the immediately preceding flower bed. The states of flower beds before that are summarized in the previous state.

This property that “the next state is determined only by the immediately previous state” is the key to applying DP.

Algorithm

DP Definition

We define the state after considering up to the \(i\)-th flower bed as follows: - \(dp[i][0]\): Maximum beauty when we do not plant a flower in the \(i\)-th flower bed - \(dp[i][1]\): Maximum beauty when we plant a flower in the \(i\)-th flower bed

Transition Equations

• Not planting: The previous flower bed can be planted or not $\(dp[i][0] = \max(dp[i-1][0], dp[i-1][1])\)$

• Planting: The previous flower bed cannot be planted (because they are adjacent) $\(dp[i][1] = dp[i-1][0] + A_i\)$

Concrete Example

For \(N = 4\), \(A = [3, 2, 5, 1]\):

\(i\)	\(A_i\)	\(dp[i][0]\) (not plant)	\(dp[i][1]\) (plant)
0	3	0	3
1	2	max(0, 3) = 3	0 + 2 = 2
2	5	max(3, 2) = 3	3 + 5 = 8
3	1	max(3, 8) = 8	3 + 1 = 4

Answer: \(\max(8, 4) = 8\) (plant in the 1st and 3rd flower beds)

Space Optimization

Since the transition only requires the immediately previous state (\(i-1\)), we can compute using just two variables instead of maintaining the entire array.

Complexity

• Time Complexity: \(O(N)\)
  • We perform constant-time computation once for each flower bed
• Space Complexity: \(O(1)\)
  • With space optimization, we only use variables to hold the previous state
  • (Additional memory excluding the input array)

Implementation Notes

• Initialization: For the first flower bed (\(i=0\)), initialize to \(0\) for not planting and \(A_0\) for planting
• Special case when \(N=1\): If there is only one flower bed, planting that flower is optimal (requires separate handling since it doesn’t enter the loop)
• Final answer: Output the larger of “planting” and “not planting” for the last flower bed

Source Code

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    
    if N == 1:
        print(A[0])
        return
    
    # dp[i][0] = maximum beauty when not planting in the i-th flower bed
    # dp[i][1] = maximum beauty when planting in the i-th flower bed
    
    # Space optimization: only keep the previous state
    prev_not_plant = 0  # maximum value when not planting in the previous flower bed
    prev_plant = A[0]   # maximum value when planting in the previous flower bed
    
    for i in range(1, N):
        # Not planting in current flower bed: previous flower bed can be planted or not
        curr_not_plant = max(prev_not_plant, prev_plant)
        # Planting in current flower bed: previous flower bed cannot be planted
        curr_plant = prev_not_plant + A[i]
        
        prev_not_plant = curr_not_plant
        prev_plant = curr_plant
    
    print(max(prev_not_plant, prev_plant))

solve()

---

This editorial was generated by claude4.5opus.