Skip to content

1788. Maximize the Beauty of the Garden 👍

  • Time: $O(n)$
  • Space: $O(n)$
 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 ans = INT_MIN;
    int prefix = 0;
    unordered_map<int, int> flowerToPrefix;

    for (const int flower : flowers) {
      if (const auto it = flowerToPrefix.find(flower);
          it != flowerToPrefix.cend())
        ans = max(ans, prefix - it->second + flower * 2);
      prefix += max(0, flower);
      if (!flowerToPrefix.count(flower))
        flowerToPrefix[flower] = prefix;
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public int maximumBeauty(int[] flowers) {
    int ans = Integer.MIN_VALUE;
    int prefix = 0;
    Map<Integer, Integer> flowerToPrefix = new HashMap<>();

    for (final int flower : flowers) {
      if (flowerToPrefix.containsKey(flower))
        ans = Math.max(ans, prefix - flowerToPrefix.get(flower) + flower * 2);
      prefix += Math.max(0, flower);
      flowerToPrefix.putIfAbsent(flower, prefix);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def maximumBeauty(self, flowers: List[int]) -> int:
    ans = -math.inf
    prefix = 0
    flowerToPrefix = collections.defaultdict(int)

    for flower in flowers:
      if flower in flowerToPrefix:
        ans = max(ans, prefix - flowerToPrefix[flower] + flower * 2)
      prefix += max(0, flower)
      flowerToPrefix.setdefault(flower, prefix)

    return ans