Maximize the beauty of the garden

Array Hash Table Greedy Prefix Sum

64.7% acceptance

Mar 31, 2026

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 ith 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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_beauty(flowers: Vec<i32>) -> i32 {
    use std::collections::HashMap;
    let n = flowers.len();
    // prefix[i] = sum of max(0, flowers[k]) for k in 0..i
    let mut prefix = vec![0i64; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i] + flowers[i].max(0) as i64;
    }
    let mut min_prefix: HashMap<i32, i64> = HashMap::new();
    let mut ans = i64::MIN;
    for j in 0..n {
      let v = flowers[j];
      if let Some(&mp) = min_prefix.get(&v) {
        // beauty = 2*v + sum of max(0, flowers[k]) for k in (i,j)
        // = 2*v + prefix[j] - prefix[i+1], minimize prefix[i+1]
        ans = ans.max(2 * v as i64 + prefix[j] - mp);
      }
      let entry = min_prefix.entry(v).or_insert(i64::MAX);
      *entry = (*entry).min(prefix[j + 1]);
    }
    ans as i32
  }
}