Formatted question description: https://leetcode.ca/all/1788.html

# 1788. Maximize the Beauty of the Garden

## Level

Hard

## Description

There is a garden of `n`

flowers, and each flower has an integer beauty value. The flowers are arranged in a line. You are given an integer array `flowers`

of size `n`

and each `flowers[i]`

represents the beauty of the `i-th`

flower.

A garden is **valid** if it meets these conditions:

- The garden has at least two flowers.
- The first and the last flower of the garden have the same beauty value.

As the appointed gardener, you have the ability to **remove** any (possibly none) flowers from the garden. You want to remove flowers in a way that makes the remaining garden **valid**. The beauty of the garden is the sum of the beauty of all the remaining flowers.

Return the maximum possible beauty of some **valid** garden after you have removed any (possibly none) flowers.

**Example 1:**

**Input:** flowers = [1,2,3,1,2]

**Output:** 8

**Explanation:** You can produce the valid garden [2,3,1,2] to have a total beauty of 2 + 3 + 1 + 2 = 8.

**Example 2:**

**Input:** flowers = [100,1,1,-3,1]

**Output:** 3

**Explanation:** You can produce the valid garden [1,1,1] to have a total beauty of 1 + 1 + 1 = 3.

**Example 3:**

**Input:** flowers = [-1,-2,0,-1]

**Output:** -2

**Explanation:** You can produce the valid garden [-1,-1] to have a total beauty of -1 + -1 = -2.

**Constraints:**

`2 <= flowers.length <= 10^5`

`-10^4 <= flowers[i] <= 10^4`

- It is possible to create a valid garden by removing some (possibly none) flowers.

## Solution

First, calculate the prefix sums of `flowers`

, but for each element in `flowers`

, only remain 0 and positive values, and make the negative values become 0.

Next, use a hash map to store each `flowers[i]`

’s first occurrence in `flowers`

. Loop over `flowers`

. For each `flowers[i]`

, obtain its first occurrence and calculate the subarray sum of the prefix sums array. Maintain the maximum beauty and return.

```
class Solution {
public int maximumBeauty(int[] flowers) {
int length = flowers.length;
int[] prefixSums = new int[length + 1];
for (int i = 0; i < length; i++)
prefixSums[i + 1] = prefixSums[i] + Math.max(0, flowers[i]);
int maxBeauty = Integer.MIN_VALUE;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < length; i++) {
int beauty = flowers[i];
if (map.containsKey(beauty)) { // first and last with the same beauty value
int firstIndex = map.get(beauty);
int beautySum = beauty * 2 + prefixSums[i] - prefixSums[firstIndex + 1];
maxBeauty = Math.max(maxBeauty, beautySum);
} else
map.put(beauty, i);
}
return maxBeauty;
}
}
```

python

```
class Solution:
def maximumBeauty(self, flowers: List[int]) -> int:
prefixSums = [0 if flowers[0] < 0 else flowers[0]]
for i in range(1, len(flowers)):
prefixSums.append(prefixSums[i-1] + (0 if flowers[i] < 0 else flowers[i]))
maxBeauty = float("-inf")
map = {}
for i in range(len(flowers)):
if flowers[i] not in map:
map[flowers[i]] = i
else:
firstIndex = map[flowers[i]]
# below is wrong for [-1,-2,0,-1] case
# sum = flowers[i] + (prefixSums[i] - prefixSums[firstIndex])
sum = flowers[i] * 2 + (prefixSums[i - 1] - prefixSums[firstIndex])
maxBeauty = max(maxBeauty, sum)
return maxBeauty
if __name__ == "__main__":
print(Solution().maximumBeauty([1,2,3,1,2]))
print(Solution().maximumBeauty([100,1,1,-3,1]))
print(Solution().maximumBeauty([-1,-2,0,-1]))
```