set + deque solution c++
Intuition\nThe elegance is a condition on both profit and category, but to simplify the problem, we can first get the maximum subsequence on profit, and improve
# Intuition\nThe elegance is a condition on both profit and category, but to simplify the problem, we can first get the maximum subsequence on profit, and improve it on the category. \n\n# Approach\n1. Sort the items by profit. So the first k items are the subsequence with maximum profits. \n2. If the first k items\' categories are all distinct, then problem is solved; however we need to check the rest items, replace the smallest duplicated items with new items on new category. \n3. I use a set to store the existing categories, and a deque to maintain the duplicates. Since the items are sorted on descending order, we should pop front items.  \n4. If the deque becomes empty, it means we don\'t have duplicates. Then we break the loop. If the new item\'s category already exists, we ignore this item. \n\n# Complexity\n- Time complexity:\nO(Nlog(N))\n\n- Space complexity:\nO(N)\n\n# Code\n```\nclass Solution {\npublic:\n    long long findMaximumElegance(vector<vector<int>>& items, int k) {\n\n        std::sort(items.begin(), items.end(), std::greater<vector<int>>());\n\n        long long cumsum = 0;\n        std::unordered_set<int> cat_set;\n        std::deque<int> duplicates;\n\n        for (int i = 0; i < k; ++i)\n        {\n            int category = items[i][1];\n            int profit = items[i][0];\n\n            cumsum += profit;\n            if (cat_set.find(category) == cat_set.end())\n            {\n                cat_set.insert(category);\n            }\n            else\n            {\n                duplicates.push_front(profit);\n            }\n        }\n\n        long long len = cat_set.size();\n        long long res = cumsum + len * len;\n\n        int sz = items.size();\n        for (int i = k; i < sz; ++i)\n        {\n            if (duplicates.empty())\n                break;\n            \n            int category = items[i][1];\n            int profit = items[i][0];\n\n            if (cat_set.find(category) != cat_set.end())\n                continue;\n            \n            int old = duplicates.front();\n            duplicates.pop_front();\n            cumsum -= old;\n            cumsum += profit;\n            cat_set.insert(category);\n\n            ++len;\n            res = std::max(res, cumsum + len * len);\n        }\n        return res;\n    }\n};\n```
['C++']