{"id":9130,"date":"2021-12-12T10:32:39","date_gmt":"2021-12-12T18:32:39","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9130"},"modified":"2021-12-12T10:36:59","modified_gmt":"2021-12-12T18:36:59","slug":"leetcode-2099-find-subsequence-of-length-k-with-the-largest-sum","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-2099-find-subsequence-of-length-k-with-the-largest-sum\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2099. Find Subsequence of Length K With the Largest Sum"},"content":{"rendered":"\n

You are given an integer array nums<\/code> and an integer k<\/code>. You want to find a subsequence <\/strong>of nums<\/code> of length k<\/code> that has the largest<\/strong> sum.<\/p>\n\n\n\n

Return <\/em>any<\/strong> such subsequence as an integer array of length <\/em>k<\/code>.<\/p>\n\n\n\n

A subsequence<\/strong> is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> nums = [2,1,3,3], k = 2\nOutput:<\/strong> [3,3]\nExplanation:<\/strong>\nThe subsequence has the largest sum of 3 + 3 = 6.<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [-1,-2,3,4], k = 3\nOutput:<\/strong> [-1,3,4]\nExplanation:<\/strong> \nThe subsequence has the largest sum of -1 + 3 + 4 = 6.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [3,4,3,3], k = 2\nOutput:<\/strong> [3,4]\nExplanation:<\/strong>\nThe subsequence has the largest sum of 3 + 4 = 7. \nAnother possible subsequence is [4, 3].\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= nums.length <= 1000<\/code><\/li>
  • -105<\/sup> <= nums[i] <= 105<\/sup><\/code><\/li>
  • 1 <= k <= nums.length<\/code><\/li><\/ul>\n\n\n\n
    Solution 1: Full sorting + Hashtable<\/strong><\/h2>\n\n\n\n
    Make a copy of the original array, sort it in whole and put k largest elements in a hashtable.<\/p>\n\n\n\n
    Scan the original array and append the number to the answer array if it’s in the hashtable.<\/p>\n\n\n\n
    Time complexity: O(nlogn)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector maxSubsequence(vector& nums, int k) {    \n    vector ans;\n    vector s(nums);\n    sort(rbegin(s), rend(s));\n    unordered_map m;\n    for (int i = 0; i < k; ++i) ++m[s[i]];\n    for (int x : nums) \n      if (--m[x] >= 0) \n        ans.push_back(x);\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
    Solution 2: k-th element<\/strong><\/h2>\n\n\n\n
    Use quick select \/ partial sort to find the k-th largest element of the array. Any number greater than that must be in the sequence. The tricky part is: what about the pivot itself? We couldn’t include ’em all blindly. Need to figure out how many copies of the pivot is there in the k largest and only include as many as of that in the final answer.<\/p>\n\n\n\n
    Time complexity: O(n+k)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector maxSubsequence(vector& nums, int k) {    \n    vector ans;\n    vector s(nums);\n    nth_element(begin(s), begin(s) + k - 1, end(s), greater());\n    const int pivot = s[k - 1];\n    \/\/ How many pivots in the largest k elements.\n    int left = count(begin(s), begin(s) + k, pivot);    \n    for (size_t i = 0; i != nums.size(); ++i)\n      if (nums[i] > pivot || (nums[i] == pivot && --left >= 0)) \n        ans.push_back(nums[i]);\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given an integer array nums and an integer k. You want to find a subsequence of nums of length k that has the largest sum. Return any such subsequence as an integer array of length k. A subsequence is…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184],"tags":[693,747,573,15],"class_list":["post-9130","post","type-post","status-publish","format-standard","hentry","category-array","tag-k-th","tag-n-th-element","tag-quickselect","tag-sorting","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9130","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=9130"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9130\/revisions"}],"predecessor-version":[{"id":9135,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9130\/revisions\/9135"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9130"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9130"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9130"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}