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 <= 105items[i].length == 2items[i][0] == profitiitems[i][1] == categoryi1 <= profiti <= 1091 <= categoryi <= n 1 <= k <= nThe brute force approach involves trying all possible solutions to find the correct one. This typically involves iterating over all possible combinations or permutations to check each possible solution.
This approach might be clear and simple, but it's often inefficient for large inputs due to its high time complexity.
This C code contains a simple placeholder function for the brute force solution. Replace the logic with the specific brute force solution code.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * m)
Space Complexity: O(1) for in-place computation.
This approach uses dynamic programming (DP) to solve the problem efficiently by breaking it down into simpler subproblems and storing the results of these subproblems to avoid redundant computations.
DP is especially useful for problems that exhibit overlapping subproblems and optimal substructure properties.
This C code provides a structure for implementing an optimized solution using dynamic programming. The actual DP logic needs to be implemented where indicated.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(n) for the DP array.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n * m) |
| Optimized Approach Using Dynamic Programming | Time Complexity: O(n) |
Longest Consecutive Sequence - Leetcode 128 • NeetCode • 904,090 views views
Watch 9 more video solutions →Practice Maximum Elegance of a K-Length Subsequence with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor