题目描述
有一个花园，有 n 朵花，这些花都有一个用整数表示的美观度。这些花被种在一条线上。给定一个长度为 n 的整数类型数组 flowers ，每一个 flowers[i] 表示第 i 朵花的美观度。
一个花园满足下列条件时，该花园是有效的。
- 花园中至少包含两朵花。
- 第一朵花和最后一朵花的美观度相同。
作为一个被钦定的园丁，你可以从花园中去除任意朵花（也可以不去除任意一朵）。你想要通过一种方法移除某些花朵，使得剩下的花园变得有效。花园的美观度是其中所有剩余的花朵美观度之和。
返回你去除了任意朵花（也可以不去除任意一朵）之后形成的有效花园中最大可能的美观度。
示例 1：
输入: flowers = [1,2,3,1,2]
输出: 8
解释: 你可以修整为有效花园 [2,3,1,2] 来达到总美观度 2 + 3 + 1 + 2 = 8。
示例 2：
输入: flowers = [100,1,1,-3,1]
输出: 3
解释: 你可以修整为有效花园 [1,1,1] 来达到总美观度 1 + 1 + 1 = 3。
示例 3：
输入: flowers = [-1,-2,0,-1]
输出: -2
解释: 你可以修整为有效花园 [-1,-1] 来达到总美观度 -1 + -1 = -2。
提示：
2 <= flowers.length <= 105-104 <= flowers[i] <= 104- 去除一些花朵（可能没有）后，是有可能形成一个有效花园的。
解法
方法一：哈希表 + 前缀和
我们用哈希表 $d$ 记录每个美观度第一次出现的位置，用前缀和数组 $s$ 记录当前位置之前的美观度之和。如果一个美观度 $v$ 在位置 $i$ 和 $j$ 出现过（其中 $i \lt j$），那么我们可以得到一个有效的花园 $[i+1,j]$，其美观度为 $s[i] - s[j + 1] + v \times 2$，我们用这个值更新答案。否则，我们将当前美观度所在的位置 $i$ 记录到哈希表 $d$ 中。接下来，我们更新前缀和，如果美观度 $v$ 为负数，我们将其视为 $0$。
遍历完所有的美观度之后，我们就可以得到答案。
时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为花朵的数量。
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution:
def maximumBeauty(self, flowers: List[int]) -> int:
s = [0] * (len(flowers) + 1)
d = {}
ans = -inf
for i, v in enumerate(flowers):
if v in d:
ans = max(ans, s[i] - s[d[v] + 1] + v * 2)
else:
d[v] = i
s[i + 1] = s[i] + max(v, 0)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | class Solution {
public int maximumBeauty(int[] flowers) {
int n = flowers.length;
int[] s = new int[n + 1];
Map<Integer, Integer> d = new HashMap<>();
int ans = Integer.MIN_VALUE;
for (int i = 0; i < n; ++i) {
int v = flowers[i];
if (d.containsKey(v)) {
ans = Math.max(ans, s[i] - s[d.get(v) + 1] + v * 2);
} else {
d.put(v, i);
}
s[i + 1] = s[i] + Math.max(v, 0);
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution {
public:
int maximumBeauty(vector<int>& flowers) {
int n = flowers.size();
vector<int> s(n + 1);
unordered_map<int, int> d;
int ans = INT_MIN;
for (int i = 0; i < n; ++i) {
int v = flowers[i];
if (d.count(v)) {
ans = max(ans, s[i] - s[d[v] + 1] + v * 2);
} else {
d[v] = i;
}
s[i + 1] = s[i] + max(v, 0);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | func maximumBeauty(flowers []int) int {
n := len(flowers)
s := make([]int, n+1)
d := map[int]int{}
ans := math.MinInt32
for i, v := range flowers {
if j, ok := d[v]; ok {
ans = max(ans, s[i]-s[j+1]+v*2)
} else {
d[v] = i
}
s[i+1] = s[i] + max(v, 0)
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | function maximumBeauty(flowers: number[]): number {
const n = flowers.length;
const s: number[] = Array(n + 1).fill(0);
const d: Map<number, number> = new Map();
let ans = -Infinity;
for (let i = 0; i < n; ++i) {
const v = flowers[i];
if (d.has(v)) {
ans = Math.max(ans, s[i] - s[d.get(v)! + 1] + v * 2);
} else {
d.set(v, i);
}
s[i + 1] = s[i] + Math.max(v, 0);
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | use std::collections::HashMap;
impl Solution {
pub fn maximum_beauty(flowers: Vec<i32>) -> i32 {
let mut s = vec![0; flowers.len() + 1];
let mut d = HashMap::new();
let mut ans = i32::MIN;
for (i, &v) in flowers.iter().enumerate() {
if let Some(&j) = d.get(&v) {
ans = ans.max(s[i] - s[j + 1] + v * 2);
} else {
d.insert(v, i);
}
s[i + 1] = s[i] + v.max(0);
}
ans
}
}
|