Skip to content

2099. Find Subsequence of Length K With the Largest Sum 👍

  • Time: $O(n) \to O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  vector<int> maxSubsequence(vector<int>& nums, int k) {
    vector<int> ans;
    vector<int> A(nums);
    nth_element(A.begin(), A.end() - k, A.end());
    const int threshold = A[A.size() - k];
    const int larger =
        ranges::count_if(nums, [&](int num) { return num > threshold; });
    int equal = k - larger;

    for (const int num : nums)
      if (num > threshold) {
        ans.push_back(num);
      } else if (num == threshold && equal) {
        ans.push_back(num);
        --equal;
      }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public int[] maxSubsequence(int[] nums, int k) {
    int[] ans = new int[k];
    int[] A = nums.clone();
    Arrays.sort(A);
    final int threshold = A[A.length - k];
    final int larger = (int) Arrays.stream(nums).filter(num -> num > threshold).count();
    int equal = k - larger;

    int i = 0;
    for (final int num : nums)
      if (num > threshold) {
        ans[i++] = num;
      } else if (num == threshold && equal > 0) {
        ans[i++] = num;
        --equal;
      }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def maxSubsequence(self, nums: list[int], k: int) -> list[int]:
    ans = []
    threshold = sorted(nums)[-k]
    larger = sum(num > threshold for num in nums)
    equal = k - larger

    for num in nums:
      if num > threshold:
        ans.append(num)
      elif num == threshold and equal:
        ans.append(num)
        equal -= 1

    return ans