> For the complete documentation index, see [llms.txt](https://zhenchaogan.gitbook.io/leetcode-solution/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zhenchaogan.gitbook.io/leetcode-solution/leetcode-1788-maximize-the-beauty-of-the-garden.md).

# LeetCode 1788. Maximize the Beauty of the Garden

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 `ith` 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:

[English Version in Youtube](https://youtu.be/3eHQSpIGvwE)

[中文版解答Youtube Link](https://youtu.be/GPgHycs-VTg)

[中文版解答Bilibili Link](https://www.bilibili.com/video/BV1uh411Q7nt/)

```
class Solution {
public:
    int maximumBeauty(vector<int>& flowers) {
        unordered_map<int, int> mymap;
        int res = INT_MIN;
        int sum = 0;
        for (int beauty : flowers) {
            if (mymap.count(beauty) > 0) {
                res = max(res, sum - mymap[beauty] + 2 * beauty);
            }
            
            if (beauty > 0) {
                sum += beauty;
            }
            
            if (mymap.count(beauty) == 0) {
                mymap[beauty] = sum;
            }
        }
        
        return res;
    }
};
```