Formatted question description: https://leetcode.ca/all/1788.html

1788. Maximize the Beauty of the Garden

Level

Hard

Description

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 i-th 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.

Example 1:

Input: flowers = [1,2,3,1,2]

Output: 8

Explanation: You can produce the valid garden [2,3,1,2] to have a total beauty of 2 + 3 + 1 + 2 = 8.

Example 2:

Input: flowers = [100,1,1,-3,1]

Output: 3

Explanation: You can produce the valid garden [1,1,1] to have a total beauty of 1 + 1 + 1 = 3.

Example 3:

Input: flowers = [-1,-2,0,-1]

Output: -2

Explanation: You can produce the valid garden [-1,-1] to have a total beauty of -1 + -1 = -2.

Constraints:

  • 2 <= flowers.length <= 10^5
  • -10^4 <= flowers[i] <= 10^4
  • It is possible to create a valid garden by removing some (possibly none) flowers.

Solution

First, calculate the prefix sums of flowers, but for each element in flowers, only remain 0 and positive values, and make the negative values become 0.

Next, use a hash map to store each flowers[i]’s first occurrence in flowers. Loop over flowers. For each flowers[i], obtain its first occurrence and calculate the subarray sum of the prefix sums array. Maintain the maximum beauty and return.

class Solution {
    public int maximumBeauty(int[] flowers) {
        int length = flowers.length;
        int[] prefixSums = new int[length + 1];
        for (int i = 0; i < length; i++)
            prefixSums[i + 1] = prefixSums[i] + Math.max(0, flowers[i]);
        int maxBeauty = Integer.MIN_VALUE;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < length; i++) {
            int beauty = flowers[i];
            if (map.containsKey(beauty)) { // first and last with the same beauty value
                int firstIndex = map.get(beauty);
                int beautySum = beauty * 2 + prefixSums[i] - prefixSums[firstIndex + 1];

                maxBeauty = Math.max(maxBeauty, beautySum);
            } else
                map.put(beauty, i);
        }
        return maxBeauty;
    }
}

python

class Solution:
    def maximumBeauty(self, flowers: List[int]) -> int:

        prefixSums = [0 if flowers[0] < 0 else flowers[0]]
        for i in range(1, len(flowers)):
            prefixSums.append(prefixSums[i-1] + (0 if flowers[i] < 0 else flowers[i]))

        maxBeauty = float("-inf")
        map = {}
        for i in range(len(flowers)):
            if flowers[i] not in map:
                map[flowers[i]] = i
            else:
                firstIndex = map[flowers[i]]

                # below is wrong for [-1,-2,0,-1] case
                # sum = flowers[i] + (prefixSums[i] - prefixSums[firstIndex])
                sum = flowers[i] * 2 + (prefixSums[i - 1] - prefixSums[firstIndex])
                maxBeauty = max(maxBeauty, sum)

        return maxBeauty


if __name__ == "__main__":
    print(Solution().maximumBeauty([1,2,3,1,2]))
    print(Solution().maximumBeauty([100,1,1,-3,1]))
    print(Solution().maximumBeauty([-1,-2,0,-1]))

All Problems

All Solutions