Problem statement

https://leetcode.com/problems/maximize-the-beauty-of-the-garden/

Solution

For each value we need to get two places: the first occurence and the last one. Also we keep acc: cumulative sums but instead of negative elements we will replace them by zeroes. So, in the end we traverse all f in places and if we have occurence more than one, we update ans.

Complexity

Time complexity is O(n), space potentially as well.

Code

class Solution:
    def maximumBeauty(self, F):
        acc = [0] + list(accumulate([max(0, f) for f in F]))
        places = defaultdict(list)
        for i, f in enumerate(F):
            places[f].append(i)

        ans = -float("inf")
        for f in places:
            if len(places[f]) >= 2:
                beg, end = places[f][0], places[f][-1]
                ans = max(ans, F[beg]*2 + acc[end] - acc[beg+1])

        return ans