Category Boosted Profit
Preview mode. Log in to edit, run, submit, and save progress.
Hard
Category Boosted Profit
A shop owner wants to decide the selling order of n items. Every item has a category and a price. When an item is sold, its profit is price multiplied by the number of different categories that have appeared among all items sold so far, including the current item. The owner may arrange the items in any order. Return the maximum total profit possible.
Examples
Example 1
Input:
1 2 1 10 20 30
Output:
110
Explanation: Sell item with category 2 first for 20 * 1, then category 1 items for 10 * 2 and 30 * 2. Total = 110.
Approach hint
For each category, one item must be sold before that category becomes active.
Common mistake
Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.
solution.cpp