Maximum Elegance of a K-Length Subsequence

Select exactly k items (each with profit and category) to maximize total_profit + (number_of_distinct_categories)^2, requiring a trade-off between picking highest-profit items (even if same category) and increasing category diversity for a quadratic bonus. The core challenge is combinatorial selection that balances sum maximization with a nonlinear reward for distinct categories.