Sorting + Traverse + Stack | O(n log n) time, O(n) space
Intuition\n Describe your first thoughts on how to solve this problem. \nTo find the maximum elegance of a subsequence with exactly k items, we need to maximize
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo find the maximum elegance of a subsequence with exactly **k** items, we need to maximize both the profit and the distinct categories. We can start by selecting the items with the top **k** profits and then explore the possibility of replacing some items to maximize distinct categories.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Sorting**: Sort the items in descending order based on profit. This ensures that the first **k** elements have the top **k** profits.\n2. **Calculate Elegance for Top k Items**: Iterate through the first **k** items, calculating the total profit and identifying distinct categories.\n3. **Identify Replaceable Items**: If there are items with repeated categories, store them in **can_remove**. They might be replaced later to increase the number of distinct categories.\n4. **Explore Replacements**: Iterate from **k** to **n**, checking if any of the remaining items introduce a new category. If yes, replace the item with the smallest profit among the repeated categories. Update the elegance after each replacement.\n5. **Return Maximum Elegance**: Return the maximum elegance after exploring all possible replacements.\n\n# Complexity\n- Time complexity: $$O(n\\log{n})$$. The sorting step takes $$O(n\\log{n})$$ time, and the subsequent operations take $$O(n)$$ time, resulting in a total time complexity of $$O(n\\log{n})$$.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$. The space complexity mainly comes from the space used to store the sorted items and the replaceable items, resulting in $$O(n)$$ space complexity.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def findMaximumElegance(self, items: List[List[int]], k: int) -> int:\n        n = len(items)\n        items.sort(reverse=True, key=lambda x: x[0]) # Sorting by profit\n        tot_profit = 0\n        categories = set()\n        distinct_categories = 0\n        can_remove = []\n        for i in range(k):\n            tot_profit += items[i][0]\n            if items[i][1] in categories:\n                can_remove.append(items[i][0]) # The element can be replaced\n            else:\n                categories.add(items[i][1])\n                distinct_categories += 1\n        ans = tot_profit + distinct_categories ** 2\n        if not can_remove:\n            return ans\n        \n        # A list of results if we replace one of the items\n        replace = [ans] * (k - distinct_categories + 1)\n        added_categories = 0 \n        for i in range(k, n):\n            if items[i][1] not in categories: # If we introduce a new category\n                added_categories += 1\n                distinct_categories += 1\n                categories.add(items[i][1])\n                tot_profit = tot_profit - can_remove[-1] + items[i][0]\n                can_remove.pop()\n                ans = tot_profit + distinct_categories ** 2 \n                replace[added_categories] = ans # Save the profit after replacement\n                if not can_remove: # No way to replace\n                    break\n        return max(replace) # Check the maximum elegance for different replacements.\n```
['Python3']