LC 2813. 子序列最大优雅度

这题看了题解，写的真好 https://leetcode.cn/problems/maximum-elegance-of-a-k-length-subsequence/solutions/2375128/fan-hui-tan-xin-pythonjavacgo-by-endless-v2w1/

他把这个算法称为”反悔贪心“，或者说这个贪心是可以撤销的。另外这题一个亮点就是有多个目标，profile和category^2.

题解给的算法非常巧妙：

首先控制住一个目标作为基准（前面K个元素）
然后看之后序列的时候，考虑一些是否可以将之前某个item给去掉（保证category数量只能增加）
同时考虑去掉这个item之后cost的改变。（减去去掉item的profile, 并且更新category数量）

class Solution:
    def findMaximumElegance(self, items: List[List[int]], k: int) -> int:
        items.sort(key=lambda x: -x[0])
        ans = 0
        total = 0

        vis = set()
        dup = []
        for i in range(len(items)):
            profit, category = items[i]
            if i < k:
                total += profit
                if category not in vis:
                    vis.add(category)
                else:
                    dup.append(profit)
            elif dup and category not in vis:
                vis.add(category)
                total += profit - dup.pop()

            ans = max(ans, total + len(vis) ** 2)
        return ans