Welcome to Subscribe On Youtube
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; } } ############ class Solution { public int maximumBeauty(int[] flowers) { int[] s = new int[flowers.length + 1]; Map<Integer, Integer> d = new HashMap<>(); int ans = Integer.MIN_VALUE; for (int i = 0; i < flowers.length; ++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; } } -
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; } }; -
class Solution: def maximumBeauty(self, flowers: List[int]) -> int: s = [0] * (len(flowers) + 1) # sum until i's previous one (inclusive) d = {} ans = -inf for i, v in enumerate(flowers): if v in d: # example input: [-1,-2,0,-1] 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 ############ 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])) -
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 } func max(a, b int) int { if a > b { return a } return b } -
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; } -
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 } }