2099: Find-Subsequence-of-Length-K-With-the-Largest-Sum
Easy

table of contents

Basically, we just want to find the k largest values of nums and return them in their original order.

We can do this by:

  1. pairing each value in nums with its respective index, pairedNums

  2. sort the array pairedNums and extract the k largest values

  3. then, simply extract the indices and place the respective values back into an ans array

code

class Solution {
public:
    vector<int> maxSubsequence(vector<int>& nums, int k) {
        vector<pair<int, int>> pairedNums;
        for (int i = 0; i < nums.size(); ++i) {
            pairedNums.push_back({nums[i], i});
        }
        sort(pairedNums.begin(), pairedNums.end(), greater());

        vector<int> indices;
        vector<int> ans;
        for (int i = 0; i < k; ++i) {
            indices.push_back(pairedNums[i].second);
        }
        
        sort(indices.begin(), indices.end());
        for (int i = 0; i < indices.size(); ++i) {
            ans.push_back(nums[indices[i]]);
        }

        return ans;
    }
};

complexity

time taken