Problem

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.

Examples

Example 1:

1
2
3
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:

1
2
3
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:

1
2
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

Method 1 – Hash Map for Prefix and Suffix Sums

Intuition

To maximize the beauty, we want the sum of a subarray where the first and last flower have the same beauty value. For each unique value, we can find the maximum sum of a subarray starting and ending with that value by tracking prefix and suffix sums.

Approach

  1. For each unique value in flowers, record all indices where it appears.
  2. For each value, for every pair of indices (left, right) with left < right, compute the sum of flowers[left:right+1].
  3. To do this efficiently, use prefix sums.
  4. Track the maximum sum for all such valid subarrays.
  5. Return the maximum found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maximumBeauty(vector<int>& flowers) {
        int n = flowers.size();
        vector<long long> pre(n+1, 0);
        for (int i = 0; i < n; ++i) pre[i+1] = pre[i] + flowers[i];
        unordered_map<int, vector<int>> pos;
        for (int i = 0; i < n; ++i) pos[flowers[i]].push_back(i);
        long long ans = LLONG_MIN;
        for (auto& [val, idxs] : pos) {
            if (idxs.size() < 2) continue;
            int l = idxs[0], r = idxs.back();
            ans = max(ans, pre[r+1] - pre[l]);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func maximumBeauty(flowers []int) int {
    n := len(flowers)
    pre := make([]int, n+1)
    for i := 0; i < n; i++ {
        pre[i+1] = pre[i] + flowers[i]
    }
    pos := map[int][]int{}
    for i, v := range flowers {
        pos[v] = append(pos[v], i)
    }
    ans := math.MinInt64
    for _, idxs := range pos {
        if len(idxs) < 2 {
            continue
        }
        l, r := idxs[0], idxs[len(idxs)-1]
        sum := pre[r+1] - pre[l]
        if sum > ans {
            ans = sum
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int maximumBeauty(int[] flowers) {
        int n = flowers.length;
        long[] pre = new long[n+1];
        for (int i = 0; i < n; i++) pre[i+1] = pre[i] + flowers[i];
        Map<Integer, List<Integer>> pos = new HashMap<>();
        for (int i = 0; i < n; i++) pos.computeIfAbsent(flowers[i], k -> new ArrayList<>()).add(i);
        long ans = Long.MIN_VALUE;
        for (var entry : pos.entrySet()) {
            List<Integer> idxs = entry.getValue();
            if (idxs.size() < 2) continue;
            int l = idxs.get(0), r = idxs.get(idxs.size()-1);
            ans = Math.max(ans, pre[r+1] - pre[l]);
        }
        return (int)ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    fun maximumBeauty(flowers: IntArray): Int {
        val n = flowers.size
        val pre = LongArray(n+1)
        for (i in 0 until n) pre[i+1] = pre[i] + flowers[i]
        val pos = mutableMapOf<Int, MutableList<Int>>()
        for (i in 0 until n) pos.getOrPut(flowers[i]) { mutableListOf() }.add(i)
        var ans = Long.MIN_VALUE
        for ((_, idxs) in pos) {
            if (idxs.size < 2) continue
            val l = idxs[0]
            val r = idxs.last()
            ans = maxOf(ans, pre[r+1] - pre[l])
        }
        return ans.toInt()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def maximumBeauty(self, flowers: list[int]) -> int:
        n = len(flowers)
        pre = [0] * (n+1)
        for i in range(n):
            pre[i+1] = pre[i] + flowers[i]
        from collections import defaultdict
        pos = defaultdict(list)
        for i, v in enumerate(flowers):
            pos[v].append(i)
        ans = float('-inf')
        for idxs in pos.values():
            if len(idxs) < 2:
                continue
            l, r = idxs[0], idxs[-1]
            ans = max(ans, pre[r+1] - pre[l])
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
impl Solution {
    pub fn maximum_beauty(flowers: Vec<i32>) -> i32 {
        let n = flowers.len();
        let mut pre = vec![0; n+1];
        for i in 0..n {
            pre[i+1] = pre[i] + flowers[i];
        }
        use std::collections::HashMap;
        let mut pos: HashMap<i32, Vec<usize>> = HashMap::new();
        for (i, &v) in flowers.iter().enumerate() {
            pos.entry(v).or_default().push(i);
        }
        let mut ans = i32::MIN as i64;
        for idxs in pos.values() {
            if idxs.len() < 2 { continue; }
            let l = idxs[0];
            let r = *idxs.last().unwrap();
            ans = ans.max(pre[r+1] as i64 - pre[l] as i64);
        }
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    maximumBeauty(flowers: number[]): number {
        const n = flowers.length;
        const pre = new Array(n+1).fill(0);
        for (let i = 0; i < n; i++) pre[i+1] = pre[i] + flowers[i];
        const pos: Record<number, number[]> = {};
        for (let i = 0; i < n; i++) {
            if (!pos[flowers[i]]) pos[flowers[i]] = [];
            pos[flowers[i]].push(i);
        }
        let ans = -Infinity;
        for (const idxs of Object.values(pos)) {
            if (idxs.length < 2) continue;
            const l = idxs[0], r = idxs[idxs.length-1];
            ans = Math.max(ans, pre[r+1] - pre[l]);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — for prefix sums and scanning all values.
  • 🧺 Space complexity: O(n) — for prefix sums and index storage.