子序列最大优雅度

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

/*
 * 使用 Java Stream API 实现：
 * 1. 首先，我们可以使用流来对 items 数组按利润排序。
 * 2. 接下来，我们可以使用 reduce 方法来计算利润的总和，同时使用 distinct 方法过滤不同类别。
 * 3. 最后，通过组合这些结果来计算优雅度。
 */

import java.util.*;
import java.util.stream.*;

public class MaxEleganceStream {
    public int findMaxElegance(int[][] items, int k) {
        List<int[]> sortedItems = Arrays.stream(items)
                .sorted((a, b) -> b[0] - a[0])
                .collect(Collectors.toList());
        
        Set<Integer> categories = new HashSet<>();
        int totalProfit = IntStream.range(0, k)
                .map(i -> {
                    categories.add(sortedItems.get(i)[1]);
                    return sortedItems.get(i)[0];
                })
                .sum();
        
        int maxElegance = totalProfit + categories.size() * categories.size();
        
        for (int i = k; i < sortedItems.size(); i++) {
            if (!categories.contains(sortedItems.get(i)[1])) {
                categories.add(sortedItems.get(i)[1]);
                totalProfit += sortedItems.get(i)[0] - sortedItems.get(k - 1)[0];
                maxElegance = Math.max(maxElegance, totalProfit + categories.size() * categories.size());
                k++;
            }
        }
        return maxElegance;
    }
}

首先按项目利润降序对items数组进行排序，确保优先选择利润最高的项目。接着，选取前k个项目作为初始子序列，计算这些项目的总利润并记录已选择的类别。如果在这前k个项目中有重复类别的项目，将其利润存入dup列表。然后，计算初始子序列的优雅度。接下来，遍历剩余的项目，如果遇到新的类别（不在已选择的类别集合中），且dup列表非空（意味着有可以替换的低利润项目），则用当前项目替换dup中的一个项目，更新总利润，并重新计算优雅度。这样，可以尝试通过添加新类别来提高优雅度，同时尽量保持高利润。最后返回遍历过程中计算的最大优雅度。

O(n log n)

O(k)