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.
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.
classSolution {
public:int maximumBeauty(vector<int>& flowers) {
int n = flowers.size();
vector<longlong> 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);
longlong 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;
}
};
funcmaximumBeauty(flowers []int) int {
n:= len(flowers)
pre:= make([]int, n+1)
fori:=0; i < n; i++ {
pre[i+1] = pre[i] +flowers[i]
}
pos:=map[int][]int{}
fori, v:=rangeflowers {
pos[v] = append(pos[v], i)
}
ans:=math.MinInt64for_, idxs:=rangepos {
if len(idxs) < 2 {
continue }
l, r:=idxs[0], idxs[len(idxs)-1]
sum:=pre[r+1] -pre[l]
ifsum > ans {
ans = sum }
}
returnans}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
classSolution {
publicintmaximumBeauty(int[] flowers) {
int n = flowers.length;
long[] pre =newlong[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
classSolution {
funmaximumBeauty(flowers: IntArray): Int {
val n = flowers.size
val pre = LongArray(n+1)
for (i in0 until n) pre[i+1] = pre[i] + flowers[i]
val pos = mutableMapOf<Int, MutableList<Int>>()
for (i in0 until n) pos.getOrPut(flowers[i]) { mutableListOf() }.add(i)
var ans = Long.MIN_VALUE
for ((_, idxs) in pos) {
if (idxs.size < 2) continueval 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
classSolution:
defmaximumBeauty(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
impl Solution {
pubfnmaximum_beauty(flowers: Vec<i32>) -> i32 {
let n = flowers.len();
letmut pre =vec![0; n+1];
for i in0..n {
pre[i+1] = pre[i] + flowers[i];
}
use std::collections::HashMap;
letmut pos: HashMap<i32, Vec<usize>>= HashMap::new();
for (i, &v) in flowers.iter().enumerate() {
pos.entry(v).or_default().push(i);
}
letmut ans =i32::MINasi64;
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] asi64- pre[l] asi64);
}
ans asi32 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
classSolution {
maximumBeauty(flowers: number[]):number {
constn=flowers.length;
constpre=new Array(n+1).fill(0);
for (leti=0; i<n; i++) pre[i+1] =pre[i] +flowers[i];
constpos: Record<number, number[]> = {};
for (leti=0; i<n; i++) {
if (!pos[flowers[i]]) pos[flowers[i]] = [];
pos[flowers[i]].push(i);
}
letans=-Infinity;
for (constidxsof Object.values(pos)) {
if (idxs.length<2) continue;
constl=idxs[0], r=idxs[idxs.length-1];
ans= Math.max(ans, pre[r+1] -pre[l]);
}
returnans;
}
}