LeetCode 1788. 最大化花园的美观度

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 <= 10^5
• -10^4 <= flowers[i] <= 10^4
• 去除一些花朵（可能没有）后，是有可能形成一个有效花园的。

提示 1

Consider every possible beauty and its first and last index in flowers.

提示 2

Remove all flowers with negative beauties within those indices.

解法：前缀和 + 哈希表

1. 前缀和的计算：

   • 我们定义 presum[i] 表示从第 0 朵花到第 i-1 朵花的美观度之和。
   • 当我们遍历到第 i 朵花时，presum[i + 1] 就是 presum[i] 加上当前花的美观度（如果是正数）。

2. 哈希表的使用：

   • 我们用哈希表 record 来记录每种美观度首次出现的位置。
   • 当我们再次遇到相同的美观度时，就可以通过前缀和快速计算该区间的美观度。

3. 计算区间美观度：

   • 对于每朵花，如果它的美观度在哈希表中已存在（即之前遇到过相同美观度的花），则我们可以计算从哈希表记录的位置到当前花之间的区间和：
     • 如果 flowers[i] 为正数，直接计算区间和：presum[i + 1] - presum[record[flowers[i]]]。
     • 如果 flowers[i] 为负数，由于负数会降低美观度，我们需要加上两倍当前美观度：presum[i + 1] - presum[record[flowers[i]]] + 2 * flowers[i]。

4. 记录首次出现位置：

   • 如果当前花的美观度 flowers[i] 不在 record 中，记录它的首次出现位置 i 。
   • 只记录第一次出现的位置，因为我们希望找到从首次出现到当前位置的区间，这样可以确保我们获得最大可能的区间美观度。

为什么只记录 flowers[i] 第一次出现的下标？

记录 flowers[i] 第一次出现的下标有以下原因：

1. 最大区间：我们希望找到尽可能长的区间，使得区间的美观度最大。记录第一次出现的位置，可以确保我们计算的区间从这个位置到当前的位置 i。
2. 唯一性：如果我们记录所有出现的位置，会增加复杂度且不必要。第一次出现的位置就足够计算当前区间的美观度。
3. 效率：记录第一次出现的位置，可以在 O(1) 时间复杂度内完成哈希表的查找和更新。

数组 flowers 中的元素组成的有效花园由该数组的一个子序列组成，子序列的首尾元素相等。为了使有效花园的美观度最大化，当花园的首尾元素值确定时，应遵循如下贪心策略。

首尾元素之间的所有元素中，只保留非负数，不保留负数。由于添加非负数使花园的美观度不变或增加，添加负数使花园的美观度减少，因此保留非负数且不保留负数的做法可以使花园的美观度最大化。

当遍历到数组 flowers 的下标 i 时，如果存在两个小于 i 的不同下标 j 和 k 满足 j<k 且 flowers[j]=flowers[k]=flowers[i]，则当选择下标 i 作为花园的结束下标时，应在下标 j 和 k 中选择较小的下标 j 作为花园的起始下标。

因为 j<k，所以数组 flowers 的下标范围 [j,i] 的子数组长度大于下标范围 [k,i] 的子数组长度，下标范围 [j,i] 中的非负数元素之和一定大于等于下标范围 [k,i] 中的非负数元素之和。

• 前缀和：用来快速计算某段区间内所有花朵的美观度之和。
• 哈希表：记录每种美观度首次出现的位置。

具体步骤如下：

1. 遍历数组，计算每个位置的前缀和。
2. 使用哈希表记录每种美观度的首次出现位置和相应的前缀和。
3. 对于每朵花的美观度，如果它在哈希表中已存在，则计算从该位置到当前位置形成的区间的美观度，并更新最大美观度。

Java版：

class Solution {
    public int maximumBeauty(int[] flowers) {
        int n = flowers.length;
        int ans = Integer.MIN_VALUE;
        int[] presum = new int[n + 1];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            presum[i + 1] = presum[i] + (flowers[i] > 0 ? flowers[i] : 0);
            if (map.containsKey(flowers[i])) {
                if (flowers[i] > 0) {
                    ans = Math.max(ans, presum[i + 1] - presum[map.get(flowers[i])]);
                } else {
                    ans = Math.max(ans, presum[i + 1] - presum[map.get(flowers[i])] + 2 * flowers[i]);
                }
            } else {
                map.put(flowers[i], i);
            }
        }
        return ans;
    }
}

Python3版：

class Solution:
    def maximumBeauty(self, flowers: List[int]) -> int:
        n = len(flowers)
        presum = [0] * (n + 1)
        ans = -inf
        record = dict()
        for i in range(n):
            presum[i + 1] = presum[i] + (flowers[i] if flowers[i] > 0 else 0)
            if flowers[i] in record:
                if flowers[i] > 0:
                    ans = max(ans, presum[i + 1] - presum[record[flowers[i]]])
                else:
                    ans = max(ans, presum[i + 1] - presum[record[flowers[i]]] + 2 * flowers[i])
            else:
                record[flowers[i]] = i 
        return ans

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 flowers 的长度。需要遍历数组一次，对于每个元素的操作时间都是 O(1)。
• 空间复杂度：O(n)，其中 n 是数组 flowers 的长度。前缀和数组和哈希表的空间都是 O(n)。

另一种写法：

Java版：

class Solution {
    public int maximumBeauty(int[] flowers) {
        int n = flowers.length;
        int ans = Integer.MIN_VALUE;
        Map<Integer, Integer> map = new HashMap<>();
        int presum = 0;
        for (int i = 0; i < flowers.length; i++) {
            if (map.containsKey(flowers[i])) {
                int nowpresum = presum + (flowers[i] > 0 ? flowers[i] : 0);
                if (flowers[i] > 0) {
                    ans = Math.max(ans, nowpresum - map.get(flowers[i]));
                } else {
                    ans = Math.max(ans, nowpresum - map.get(flowers[i]) + 2 * flowers[i]);
                }
            } else {
                map.put(flowers[i], presum);
            }
            presum += flowers[i] > 0 ? flowers[i] : 0;
        }
        return ans;
    }
}

 Python3版：

class Solution:
    def maximumBeauty(self, flowers: List[int]) -> int:
        ans = -inf
        presum = 0
        record = dict()
        for i in range(len(flowers)):
            if flowers[i] in record:
                nowpresum = presum + (flowers[i] if flowers[i] > 0 else 0)
                if flowers[i] > 0:
                    ans = max(ans, nowpresum - record[flowers[i]])
                else:
                    ans = max(ans, nowpresum - record[flowers[i]] + 2 * flowers[i])
            else:
                record[flowers[i]] = presum 
            presum += flowers[i] if flowers[i] > 0 else 0
        return ans

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 flowers 的长度。需要遍历数组一次，对于每个元素的操作时间都是 O(1)。
• 空间复杂度：O(n)，其中 n 是数组 flowers 的长度。哈希表的空间是 O(n)。