We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximize the Beauty of the Garden

Number: 1937

Difficulty: Hard

Paid? Yes

Companies: Amazon

Problem Description

Given an array of integers representing the beauty of n flowers arranged in a line, you are allowed to remove any (possibly none) of the flowers. The resulting garden (which is a subsequence of the original) must have at least two flowers and the first and last flower in the subsequence must have the same beauty value. You need to maximize the total beauty (sum) of the resulting valid garden.

Key Insights

  • The selected valid garden is a subsequence of the original array with arbitrary removals; order is preserved.
  • You must choose two positions (i and j, i < j) such that flowers[i] == flowers[j]. These serve as the fixed start and end of the valid garden.
  • For the elements between these two indices, you can pick any subset. Thus, you should only add flowers with positive beauty values, since including negatives would decrease the total sum.
  • Precompute a prefix sum array over positive values to quickly compute the sum of all positive beauties in any segment.
  • For each unique flower value that appears at least twice, iterate over its indices to compute the maximum achievable beauty using the formula: TotalBeauty = 2 * (flower value) + (sum of positive values between the chosen indices), which can be computed as 2*v + (prefix[j] – prefix[i+1]).
  • Use a dictionary (or hash table) to map each flower beauty value to all its indices and then use a greedy scan with maintained minimum prefix value for candidates.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

We first compute a prefix sum array over the input array where each element contributes its value only if it is positive (zero otherwise). This lets us quickly compute the maximum sum we can add from any segment (skipping negatives). Then, for each unique flower value v that appears at least twice, we traverse its sorted indices list. While scanning, maintain the minimum prefix sum at positions corresponding to (index+1) from previous occurrences. For each subsequent occurrence, compute a candidate sum as 2*v (for the two chosen endpoints) plus the difference between the current prefix value and the previously maintained minimum prefix. Take the maximum over all candidates from every flower type as the answer.

Key data structures:

  • A prefix sum array over positive values.
  • A hash map from flower value to a list of indices (occurrence positions).

Algorithmic approach:

  • Build the prefix sum array.
  • Build the dictionary mapping each flower value to its list of occurrence indices.
  • For each flower value with at least two occurrences, use a greedy two-pointer style scan to compute the best candidate sum.
  • Return the maximum candidate sum across all valid flower values.

Code Solutions

# Python solution with detailed comments
class Solution:
    def maximumBeauty(self, flowers: List[int]) -> int:
        n = len(flowers)
        # Build prefix sum: only add positive values.
        pos_prefix = [0] * (n + 1)
        for i in range(n):
            # Only include the flower if it is positive.
            pos_prefix[i+1] = pos_prefix[i] + (flowers[i] if flowers[i] > 0 else 0)
        
        # Map each flower value to its list of indices.
        from collections import defaultdict
        indices_map = defaultdict(list)
        for i, beauty in enumerate(flowers):
            indices_map[beauty].append(i)
        
        # Initialize the answer as negative infinity.
        max_beauty = float('-inf')
        
        # Iterate for each flower value that appears at least twice.
        for v, positions in indices_map.items():
            if len(positions) < 2:
                continue
            # Initialize the minimum prefix value using the first occurrence.
            min_prefix = pos_prefix[positions[0] + 1]
            # For every subsequent occurrence, calculate total possible beauty.
            for j in positions[1:]:
                # Total sum = value of first endpoint and last endpoint (both equal v)
                # plus sum of positive values between the chosen indices.
                # This sum of positives is: pos_prefix[j] - min_prefix.
                candidate = 2 * v + (pos_prefix[j] - min_prefix)
                max_beauty = max(max_beauty, candidate)
                # Update the minimum prefix using the current index’s prefix (for future pairs).
                min_prefix = min(min_prefix, pos_prefix[j])
        
        return max_beauty
← Back to All Questions