[Python3] Greedy
Intuition\n\nSay an item is golden if it has the highest profit in its category.\n\nSuppose we use $C$ categories in our selection.  It consists of the most pro
**Intuition**\n\nSay an item is *golden* if it has the highest profit in its category.\n\nSuppose we use $C$ categories in our selection.  It consists of the most profitable $C$ golden items, and the rest of the items are chosen to be the ones with the highest profit.\n\n**Algorithm**\n\nSort `items` decreasing by profit.  When you encounter an item with a new category, it must be golden.  Otherwise it is a duplicate.\n\nWe\'re keeping track of `cates`, the set of categories with a golden item, `dupes`, the list of profit of duplicate items, and `cur`, the current total profit.\n\n\n# Code\n```\nclass Solution:\n    def findMaximumElegance(self, items, K):\n        items.sort(reverse=True)\n        \n        dupes = []\n        cates = set()\n        ans = cur = 0\n        for p, c in items:\n            cur += p\n            if c not in cates:\n                cates.add(c)\n            else:\n                dupes.append(p)\n\n            while dupes and len(dupes) + len(cates) > K:\n                cur -= dupes.pop()\n            if len(dupes) + len(cates) <= K:\n                ans = max(ans, cur + len(cates) ** 2)\n        \n        return ans\n```
['Python3']