#1403
Minimum Subsequence in Non-Increasing Order
pupil · 305 · lc easy +21 · verified · 73.6% accepted · 634 likes · top 84%
Description
Given the array nums, find a subsequence whose element sum is strictly greater than the sum of the remaining elements. Among all such subsequences, return the one with the fewest elements; if still tied, return the one with the greatest total sum. A subsequence is obtained by removing some (possibly zero) elements while preserving order.
Return the answer in non-increasing order. The solution is guaranteed to be unique.
Example 1:
Input: nums = [4,3,10,9,8]
Output: [10,9]
Explanation: 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.
Example 2:
Input: nums = [4,4,7,6,7]
Output: [7,7,6]
Explanation: 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 be returned in non-increasing order.
Code
1
2
3