Description
Given an array nums, return a subsequence with the largest sum such that the sum is strictly greater than the sum of the non-included elements. Return in non-increasing order.
Examples
Input:
nums = [4,3,10,9,8]Output:
[10,9]Explanation:
Sorted descending: [10,9,8,4,3]. Take 10 and 9 (sum=19), remaining sum=15. Since 19 > 15, return [10,9].
Input:
nums = [1,2,3,4,5]Output:
[5,4]Explanation:
The array sorted in non-increasing order is [5,4,3,2,1]. Taking elements greedily: 5 gives sum 5, but 5 <= 10 (remaining sum). Adding 4 gives sum 9, and 9 > 6 (remaining sum), so the result is [5,4].
Input:
nums = [6]Output:
[6]Explanation:
With only one element, it must be taken to form the subsequence. The sum 6 > 0 (remaining sum), so the answer is [6].
Constraints
- •
1 ≤ nums.length ≤ 500