Coding

Maximize the Beauty of the Garden

Asked at

ServiceNow

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an integer array flowers of size n, where flowers[i] denotes the beauty of the i-th flower. The flowers are positioned in a straight line

A valid garden must satisfy the following conditions:

It contains at least two flowers.
The first and last flower of the selected garden must have the same beauty value.

The task is to remove any number of flowers (including none) to create a valid garden. The beauty of a valid garden is the sum of the beauty values of all flowers in it. Return the maximum possible beauty of any valid garden that can be formed after removing flowers.

Input: flowers = [2, 4, 6, 2, 5] Output: 14 Explanation: You can select the valid garden [2, 4, 6, 2], where the first and last flowers have the same beauty value (2). Total beauty = 2 + 4 + 6 + 2 = 14.

Input: flowers = [50, 5, 5, -10, 5] Output: 15 Explanation: The valid garden [5, 5, 5] gives a total beauty of 5 + 5 + 5 = 15.

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

n == flowers.length
2 ≤ n ≤ 105
-105 ≤ flowers[i] ≤ 105

cpp

class Solution {
public:
    int maximumBeauty(vector<int>& flowers) {
       
    }
};

java

class Solution {
    public int maximumBeauty(int[] flowers) {
     
    }
}

python

class Solution:
    def maximumBeauty(self, flowers):

javascript

class Solution {
    maximumBeauty(flowers) {

    }
}

csharp

public class Solution {
    public long MaximumBeauty(IList<int> flowers) {
        // User's implementation goes here
    }
}

func maximumBeauty(flowers []int) int {
    // Your code goes here
}

Stuck? Show a way to structure it+

01Maintain a running prefix sum.
02For each beauty value, remember the best prefix before an earlier equal value.
03When the value repeats, form a candidate interval.
04Update the best answer.
05Update that value's stored prefix minimum.

Reference answer

A valid garden is a subsequence whose first and last selected flowers have equal values; because removing negative interior flowers is allowed, be precise about the variant. For the stated contiguous interpretation, use prefix sums: an interval [i, j] with equal endpoints has sum prefix[j + 1] - prefix[i]. For each beauty value, retain the smallest prefix sum seen immediately before an occurrence of that value. On reaching value x at j, combine prefix[j + 1] with that stored minimum to form the best interval ending at j, then update the stored minimum with prefix[j]. Require two occurrences by only evaluating a value after it was seen earlier. Use long because values and sums can exceed int. The scan is O(N) time and O(N) expected space for the map.

Then expect these follow-ups

How would you solve the subsequence variant with negative interior values?
Tests: problem interpretation
How do you reconstruct the chosen endpoints?
Tests: index tracking

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question