Find Subsequence of Length K With the Largest Sum LeetCode solution in C++

1
// OJ:
2
// https://leetcode.com/problems/find-subsequence-of-length-k-with-the-largest-sum/
3
// Author: github.com/lzl124631x
4
// Time: O(NlogN)
5
// Space: O(N)
6
class Solution {
7
 public:
8
  vector<int> maxSubsequence(vector<int> &A, int k) {
9
    vector<int> id(A.size());
10
    iota(begin(id), end(id), 0); // Index array 0, 1, 2, ...
11
    sort(begin(id), end(id),
12
         [&](int a, int b) { return A[a] > A[b]; }); // Sort the indexes in descending order of
13
                                                     // their corresponding values in `A`
14
    id.resize(k);             // Only keep the first `k` indexes with the greatest `A` values
15
    sort(begin(id), end(id)); // Sort indexes in ascending order
16
    vector<int> ans;
17
    for (int i : id) ans.push_back(A[i]);
18
    return ans;
19
  }
20
};