{"id":6575,"date":"2020-04-04T22:05:30","date_gmt":"2020-04-05T05:05:30","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6575"},"modified":"2020-04-04T22:11:28","modified_gmt":"2020-04-05T05:11:28","slug":"leetcode-1403-minimum-subsequence-in-non-increasing-order","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-1403-minimum-subsequence-in-non-increasing-order\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1403. Minimum Subsequence in Non-Increasing Order"},"content":{"rendered":"\n

Given the array nums<\/code>, obtain a subsequence of the array whose sum of elements is strictly greater<\/strong> than the sum of the non included elements in such subsequence. <\/p>\n\n\n\n

If there are multiple solutions, return the subsequence with minimum size<\/strong> and if there still exist multiple solutions, return the subsequence with the maximum total sum<\/strong> of all its elements. A subsequence of an array can be obtained by erasing some (possibly zero) elements from the array. <\/p>\n\n\n\n

Note that the solution with the given constraints is guaranteed to be unique<\/strong>. Also return the answer sorted in non-increasing<\/strong> order.<\/p>\n\n\n\n

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

Input:<\/strong> nums = [4,3,10,9,8]\nOutput:<\/strong> [10,9] \nExplanation:<\/strong> The subsequences [10,9] and [10,8] are minimal such that the sum of their elements is strictly greater than the sum of elements not included, however, the subsequence [10,9] has the maximum total sum of its elements. \n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [4,4,7,6,7]\nOutput:<\/strong> [7,7,6] \nExplanation:<\/strong> The subsequence [7,7] has the sum of its elements equal to 14 which is not strictly greater than the sum of elements not included (14 = 4 + 4 + 6). Therefore, the subsequence [7,6,7] is the minimal satisfying the conditions. Note the subsequence has to returned in non-decreasing order.  \n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [6]\nOutput:<\/strong> [6]\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= nums.length <= 500<\/code><\/li>
  • 1 <= nums[i] <= 100<\/code><\/li><\/ul>\n\n\n\n
    Solution: Greedy<\/strong><\/h2>\n\n\n\n
    Sort the elements in reverse order, pick the largest elements until their sum is greater than the sum of the left elements or total \/ 2.<\/p>\n\n\n\n
    Time complexity: O(nlogn)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector minSubsequence(vector& nums) {\n    sort(rbegin(nums), rend(nums));\n    int total = accumulate(begin(nums), end(nums), 0);\n    vector ans;\n    int sum = 0;\n    for (int v : nums) {\n      sum += v;\n      ans.push_back(v);\n      if (sum > total \/ 2) break;\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Given the array nums, obtain a subsequence of the array whose sum of elements is strictly greater than the sum of the non included elements in such subsequence.  If…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[51],"tags":[20,222,88],"class_list":["post-6575","post","type-post","status-publish","format-standard","hentry","category-greedy","tag-array","tag-easy","tag-greedy","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6575","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=6575"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6575\/revisions"}],"predecessor-version":[{"id":6577,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6575\/revisions\/6577"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6575"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6575"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6575"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}