Maximize the Beauty of the Garden

Maximize the Beauty of the Garden

What is this problem about?

The Maximize the Beauty of the Garden problem provides an array of integers representing the "beauty" of flowers in a garden. You can pluck any number of flowers from the garden. Your goal is to find the maximum possible beauty of a contiguous subarray, but with a strict condition: the first flower and the last flower of your chosen subarray must have the exact same beauty value.

Why is this asked in interviews?

This is a fantastic problem that combines Hash Maps with Prefix Sums. Interviewers ask it because it forces candidates to evaluate optimal inclusion. A naive approach would find all matching pairs and sum everything between them. But since flower beauties can be negative, you shouldn't just blindly sum everything. It tests if you know how to selectively filter negative values while maintaining the required boundary conditions.

Algorithmic pattern used

This problem relies on a Prefix Sum of Positives and a Hash Map.

1. Since we can pluck (remove) any flower, we should obviously remove all flowers with negative beauty that lie between our two boundary flowers.
2. We create a prefix sum array that ONLY accumulates positive numbers. (e.g., if arr[i] > 0: prefix[i] = prefix[i-1] + arr[i]).
3. We use a Hash Map to store the first occurrence index of every flower beauty value.
4. As we iterate through the array, if we see a flower beauty we've seen before at first_idx, we calculate the score: beauty_value * 2 + (prefix[current_idx - 1] - prefix[first_idx]). We track the global maximum of these valid sequences.

Example explanation

Array: [1, 2, -1, 3, 1]

1. Positive Prefix Sum: [1, 3, 3, 6, 7] (The -1 is ignored, so the sum doesn't change).
2. Iterate and track first occurrences:

• 1 (idx 0): Map {1: 0}.
• 2 (idx 1): Map {1: 0, 2: 1}.
• -1 (idx 2): Map {1: 0, 2: 1, -1: 2}.
• 3 (idx 3): Map {1: 0, 2: 1, -1: 2, 3: 3}.
• 1 (idx 4): We've seen 1 before at index 0!
  • The boundaries are 1 and 1. They contribute $1 + 1 = 2$.
  • The positive sum between them (indices 1 to 3): prefix[3] - prefix[0] = $6 - 1 = 5$.
  • Total beauty = $2 + 5 = 7$. The maximum beauty is 7. (We keep [1, 2, 3, 1] and pluck the -1).

Common mistakes candidates make

A very common mistake is forgetting that the boundary flowers themselves might be negative! If the boundary flower is -5, you must include both -5s in your sum, even though your prefix array filters out negatives. The formula 2 * boundary_val + positive_sum_between correctly forces the inclusion of the boundaries regardless of their sign.

Interview preparation tip

When tackling the Maximize the Beauty of the Garden coding problem, or any problem where you can "delete elements to maximize a sum," remember that you should simply ignore negative numbers. A "Positive-Only Prefix Sum" is an incredibly powerful tool that solves subsequence maximization problems in $O(N)$ time effortlessly.