2813. Maximum Elegance of a K-Length Subsequence Hard

1/**
2 * [2813] Maximum Elegance of a K-Length Subsequence
3 *
4 * You are given a 0-indexed 2D integer array items of length n and an integer k.
5 * items[i] = [profiti, categoryi], where profiti and categoryi denote the profit and category of the i^th item respectively.
6 * Let's define the elegance of a subsequence of items as total_profit + distinct_categories^2, 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.
7 * Your task is to find the maximum elegance from all subsequences of size k in items.
8 * Return an integer denoting the maximum elegance of a subsequence of items with size exactly k.
9 * 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.
10 *  
11 * <strong class="example">Example 1:
12 * 
13 * Input: items = [[3,2],[5,1],[10,1]], k = 2
14 * Output: 17
15 * Explanation: In this example, we have to select a subsequence of size 2.
16 * We can select items[0] = [3,2] and items[2] = [10,1].
17 * The total profit in this subsequence is 3 + 10 = 13, and the subsequence contains 2 distinct categories [2,1].
18 * Hence, the elegance is 13 + 2^2 = 17, and we can show that it is the maximum achievable elegance. 
19 * 
20 * <strong class="example">Example 2:
21 * 
22 * Input: items = [[3,1],[3,1],[2,2],[5,3]], k = 3
23 * Output: 19
24 * Explanation: In this example, we have to select a subsequence of size 3. 
25 * We can select items[0] = [3,1], items[2] = [2,2], and items[3] = [5,3]. 
26 * The total profit in this subsequence is 3 + 2 + 5 = 10, and the subsequence contains 3 distinct categories [1,2,3]. 
27 * Hence, the elegance is 10 + 3^2 = 19, and we can show that it is the maximum achievable elegance.
28 * <strong class="example">Example 3:
29 * 
30 * Input: items = [[1,1],[2,1],[3,1]], k = 3
31 * Output: 7
32 * Explanation: In this example, we have to select a subsequence of size 3. 
33 * We should select all the items. 
34 * The total profit will be 1 + 2 + 3 = 6, and the subsequence contains 1 distinct category [1]. 
35 * Hence, the maximum elegance is 6 + 1^2 = 7.  
36 *  
37 * Constraints:
38 * 
39 * 	1 <= items.length == n <= 10^5
40 * 	items[i].length == 2
41 * 	items[i][0] == profiti
42 * 	items[i][1] == categoryi
43 * 	1 <= profiti <= 10^9
44 * 	1 <= categoryi <= n 
45 * 	1 <= k <= n
46 * 
47 */
48pub struct Solution {}
49
50// problem: https://leetcode.com/problems/maximum-elegance-of-a-k-length-subsequence/
51// discuss: https://leetcode.com/problems/maximum-elegance-of-a-k-length-subsequence/discuss/?currentPage=1&orderBy=most_votes&query=
52
53// submission codes start here
54
55impl Solution {
56    pub fn find_maximum_elegance(items: Vec<Vec<i32>>, k: i32) -> i64 {
57        
58    }
59}
60
61// submission codes end
62
63#[cfg(test)]
64mod tests {
65    use super::*;
66
67    #[test]
68    fn test_2813() {
69    }
70}
71