#2813
Maximum Elegance of a K-Length Subsequence
international master · 2015 · lc hard +32 · verified · 28.5% accepted · 323 likes · top 6%
Description
A 0-indexed 2D integer array items of length n is given, along with an integer k. Each items[i] = [profiti, categoryi].
Define the elegance of a subsequence of items as total_profit + distinct_categories2, where total_profit is the sum of profits and distinct_categories is the number of distinct categories.
Among all subsequences of exactly k items, return the maximum elegance.
Note: A subsequence is formed by deleting some elements (possibly none) without changing the remaining order.
Example 1:
Input: items = [[3,2],[5,1],[10,1]], k = 2
Output: 17
Explanation: In this example, we have to select a subsequence of size 2.
We can select items[0] = [3,2] and items[2] = [10,1].
The total profit in this subsequence is 3 + 10 = 13, and the subsequence contains 2 distinct categories [2,1].
Hence, the elegance is 13 + 22 = 17, and we can show that it is the maximum achievable elegance.
Example 2:
Input: items = [[3,1],[3,1],[2,2],[5,3]], k = 3
Output: 19
Explanation: In this example, we have to select a subsequence of size 3.
We can select items[0] = [3,1], items[2] = [2,2], and items[3] = [5,3].
The total profit in this subsequence is 3 + 2 + 5 = 10, and the subsequence contains 3 distinct categories [1,2,3].
Hence, the elegance is 10 + 32 = 19, and we can show that it is the maximum achievable elegance.
Example 3:
Input: items = [[1,1],[2,1],[3,1]], k = 3
Output: 7
Explanation: In this example, we have to select a subsequence of size 3.
We should select all the items.
The total profit will be 1 + 2 + 3 = 6, and the subsequence contains 1 distinct category [1].
Hence, the maximum elegance is 6 + 12 = 7.
Code
1
2
3