class Solution {
public:
int maximumBeauty(vector<int>& flowers) {
}
};
1788. 最大化花园的美观度
有一个花园，有 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原站题解
java 解法, 执行用时: 9 ms, 内存消耗: 54.6 MB, 提交时间: 2023-10-21 23:37:44
class Solution {
public int maximumBeauty(int[] flowers) {
int n = flowers.length;
int[] sumPositive = new int[n + 1];
int[] left = new int[20010], right = new int[20010];
Arrays.fill(left, -1);
Arrays.fill(right, -1);
for (int i = 1; i <= n; ++ i) {
int f = flowers[i - 1];
sumPositive[i] = f >= 0 ? sumPositive[i - 1] + f : sumPositive[i - 1];
if (left[f + 10000] == -1) left[f + 10000] = i - 1;
right[f + 10000] = i - 1;
}
int ans = 0x80000000;
for (int i = 0; i < n; ++ i) {
int f = flowers[i];
int l = left[f + 10000], r = right[f + 10000];
if (l == r) continue;
int sum = f * 2 + sumPositive[r] - sumPositive[l + 1];
ans = Math.max(ans, sum);
}
return ans;
}
}
cpp 解法, 执行用时: 64 ms, 内存消耗: 54.6 MB, 提交时间: 2023-10-21 23:37:16
class Solution {
public:
int maximumBeauty(vector<int>& flowers) {
unordered_map<int, int> mp; // 存放值及对应的前缀和
int ans = INT_MIN, preSum = 0;
for (auto f:flowers) {
if (f > 0) preSum += f; // 计算前缀和时不计算负数
if (mp.count(f)) { // 如果之前存在相同的数，则更新答案
ans = max(ans, preSum - mp[f] + (f > 0 ? f : 2 * f));
} else { // 若之前不存在，则插入
mp[f] = preSum;
}
}
return ans;
}
};
python3 解法, 执行用时: 172 ms, 内存消耗: 29.4 MB, 提交时间: 2023-10-21 23:37:05
class Solution:
def maximumBeauty(self, flowers: List[int]) -> int:
pre=[0]*(len(flowers)+1)
res=-inf
dic={}
for i,v in enumerate(flowers):
pre[i+1]=pre[i]
if v in dic:
# 计算两个相同值之间正数之和+值本身*2
res=max(res,pre[i]-pre[dic[v]+1]+v*2)
else:
dic[v]=i
# 前缀和仅仅累加正数
if v>0:
pre[i+1]+=v
return res
golang 解法, 执行用时: 64 ms, 内存消耗: 9.3 MB, 提交时间: 2023-10-21 23:35:51
func maximumBeauty(a []int) int {
sum := make([]int, len(a)+1)
r := map[int]int{}
for i, v := range a {
sum[i+1] = sum[i] + max(v, 0) // 将所有负数去掉
r[v] = i // 记录每个元素出现的最右位置
}
ans := int(-1e9)
for i, v := range a {
if r[v] > i {
ans = max(ans, v*2+sum[r[v]]-sum[i+1]) // 计算 a[i] + a[r[a[i]]] + [i+1,r[v]) 的所有非负数
}
}
return ans
}
func max(a, b int) int { if b > a { return b }; return a }