Algorithms
Hard
2813
2894
Maximum Elegance of a K-Length Subsequence
maximum-elegance-of-a-k-length-subsequence
"""
You are given a 0-indexed 2D integer array items of length n and an integer k.

items[i] = [profiti, categoryi], where profiti and categoryi denote the profit and category of the ith item respectively.

Let's define the elegance of a subsequence of items as total_profit + distinct_categories2, where total_profit is the sum of all profits in the subsequence, and distinct_categories is the number of distinct categories from all the categories in the selected subsequence.

Your task is to find the maximum elegance from all subsequences of size k in items.

Return an integer denoting the maximum elegance of a subsequence of items with size exactly k.

Note: A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements' relative 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.

Constraints:

 * 1 <= items.length == n <= 105
 * items[i].length == 2
 * items[i][0] == profiti
 * items[i][1] == categoryi
 * 1 <= profiti <= 109
 * 1 <= categoryi <= n
 * 1 <= k <= n
"""
class Solution:
    def findMaximumElegance(self, items: List[List[int]], k: int) -> int:
        
You are given a 0-indexed 2D integer array items of length n and an integer k.

items[i] = [profiti, categoryi], where profiti and categoryi denote the profit and category of the ith item respectively.

Let's define the elegance of a subsequence of items as total_profit + distinct_categories2, where total_profit is the sum of all profits in the subsequence, and distinct_categories is the number of distinct categories from all the categories in the selected subsequence.

Your task is to find the maximum elegance from all subsequences of size k in items.

Return an integer denoting the maximum elegance of a subsequence of items with size exactly k.

Note: A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements' relative 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.

Constraints:

 * 1 <= items.length == n <= 105
 * items[i].length == 2
 * items[i][0] == profiti
 * items[i][1] == categoryi
 * 1 <= profiti <= 109
 * 1 <= categoryi <= n
 * 1 <= k <= n


Please complete the code below to solve above prblem:
```python
class Solution:
    def findMaximumElegance(self, items: List[List[int]], k: int) -> int:
        
```

my_solution = Solution()

test_input = { "items": [[3,2],[5,1],[10,1]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 17

test_input = { "items": [[3,1],[3,1],[2,2],[5,3]], "k": 3 }
assert my_solution.findMaximumElegance(**test_input) == 19

test_input = { "items": [[1,1],[2,1],[3,1]], "k": 3 }
assert my_solution.findMaximumElegance(**test_input) == 7

test_input = { "items": [[1,1],[1,2]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 6

test_input = { "items": [[1,1],[4,1]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 5

test_input = { "items": [[1,1],[4,1]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 6

test_input = { "items": [[1,1],[6,1]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 7

test_input = { "items": [[1,1],[6,1]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 8

test_input = { "items": [[1,1],[8,2]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 13

test_input = { "items": [[1,2],[6,2]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 7

test_input = { "items": [[1,2],[10,1]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 11

test_input = { "items": [[2,1],[6,1]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 9

test_input = { "items": [[2,1],[7,1]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 10

test_input = { "items": [[2,1],[9,2]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 10

test_input = { "items": [[2,2],[2,2]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 3

test_input = { "items": [[2,2],[2,2]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 5

test_input = { "items": [[2,2],[3,1]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 9

test_input = { "items": [[2,2],[6,1]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 12

test_input = { "items": [[3,1],[1,2]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 8

test_input = { "items": [[3,1],[9,1]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 13

test_input = { "items": [[3,1],[9,2]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 10

test_input = { "items": [[3,1],[10,2]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 17

test_input = { "items": [[3,2],[3,1]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 4

test_input = { "items": [[3,2],[5,2]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 6

test_input = { "items": [[3,2],[10,1]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 17

test_input = { "items": [[3,2],[10,2]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 14

test_input = { "items": [[4,1],[7,2]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 15

test_input = { "items": [[4,1],[9,2]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 10

test_input = { "items": [[4,2],[2,1]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 10

test_input = { "items": [[4,2],[3,1]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 11

test_input = { "items": [[4,2],[5,2]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 6

test_input = { "items": [[4,2],[7,2]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 8

test_input = { "items": [[4,2],[8,1]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 16

test_input = { "items": [[4,2],[10,1]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 18

test_input = { "items": [[5,1],[4,2]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 6

test_input = { "items": [[5,1],[8,1]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 14

test_input = { "items": [[5,1],[8,2]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 9

test_input = { "items": [[5,1],[9,1]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 10

test_input = { "items": [[5,2],[2,1]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 6

test_input = { "items": [[5,2],[4,2]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 10

test_input = { "items": [[5,2],[5,1]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 14

test_input = { "items": [[6,1],[1,1]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 7

test_input = { "items": [[6,1],[4,1]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 7

test_input = { "items": [[6,1],[7,1]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 8

test_input = { "items": [[6,1],[7,2]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 17

test_input = { "items": [[6,1],[8,1]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 15

test_input = { "items": [[6,1],[8,2]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 18

test_input = { "items": [[6,1],[9,1]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 10

test_input = { "items": [[6,2],[2,1]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 7

test_input = { "items": [[6,2],[4,2]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 7

test_input = { "items": [[6,2],[5,1]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 7

test_input = { "items": [[6,2],[6,2]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 7

test_input = { "items": [[6,2],[6,2]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 13

test_input = { "items": [[6,2],[7,1]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 8

test_input = { "items": [[6,2],[7,1]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 17

test_input = { "items": [[6,2],[8,2]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 15

test_input = { "items": [[6,2],[10,2]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 17

test_input = { "items": [[7,1],[1,1]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 8

test_input = { "items": [[7,1],[3,2]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 8

test_input = { "items": [[7,1],[6,1]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 14

test_input = { "items": [[7,2],[5,1]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 16

test_input = { "items": [[7,2],[5,2]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 8

test_input = { "items": [[7,2],[7,2]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 15

test_input = { "items": [[7,2],[10,2]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 18

test_input = { "items": [[8,1],[2,1]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 9

test_input = { "items": [[8,1],[2,2]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 9

test_input = { "items": [[8,1],[4,2]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 9

test_input = { "items": [[8,1],[5,1]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 9

test_input = { "items": [[8,1],[6,2]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 9

test_input = { "items": [[8,1],[8,1]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 17

test_input = { "items": [[8,1],[9,1]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 10

test_input = { "items": [[8,1],[9,2]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 21

test_input = { "items": [[8,2],[1,1]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 9

test_input = { "items": [[8,2],[1,2]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 9

test_input = { "items": [[8,2],[2,1]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 9

test_input = { "items": [[8,2],[8,2]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 9

test_input = { "items": [[8,2],[9,1]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 21

test_input = { "items": [[8,2],[9,2]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 18

test_input = { "items": [[8,2],[10,1]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 22

test_input = { "items": [[9,1],[1,1]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 10

test_input = { "items": [[9,1],[3,2]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 16

test_input = { "items": [[9,1],[4,2]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 17

test_input = { "items": [[9,1],[6,2]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 10

test_input = { "items": [[9,1],[9,2]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 10

test_input = { "items": [[9,1],[10,2]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 11

test_input = { "items": [[9,2],[1,2]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 10

test_input = { "items": [[9,2],[2,1]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 15

test_input = { "items": [[9,2],[6,1]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 19

test_input = { "items": [[9,2],[6,2]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 16

test_input = { "items": [[9,2],[8,2]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 10

test_input = { "items": [[10,1],[2,2]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 11

test_input = { "items": [[10,1],[4,2]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 11

test_input = { "items": [[10,1],[5,1]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 16

test_input = { "items": [[10,1],[5,2]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 19

test_input = { "items": [[10,1],[7,1]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 11

test_input = { "items": [[10,2],[1,2]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 11

test_input = { "items": [[10,2],[4,1]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 11

test_input = { "items": [[10,2],[5,1]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 11

test_input = { "items": [[10,2],[7,1]], "k": 1 }
assert my_solution.findMaximumElegance(**test_input) == 11

test_input = { "items": [[10,2],[8,2]], "k": 2 }
assert my_solution.findMaximumElegance(**test_input) == 19