Minimum Subsequence in Non-Increasing Order

The problem is asking for a subsequence of the given array nums such that the sum of the elements in this subsequence is strictly greater than the sum of the elements not in the subsequence. If there are multiple solutions, we want the one with the minimum size and the maximum total sum, and the result should be sorted in non-increasing order.

Approach

• Sort the Array: Sort the given array nums in non-increasing order. This ensures that we can construct the subsequence with the minimum size and maximum sum.
• Initialize Variables: Initialize a variable total_sum to store the sum of all elements in the array. Initialize another variable current_sum to store the sum of elements in the current subsequence. Set total_sum as the sum of all elements in nums and current_sum to 0.
• Iterate and Build Subsequence: Iterate through the sorted array, adding elements to the subsequence until the current_sum becomes greater than half of the total_sum. This ensures that the sum of the subsequence is strictly greater than the sum of the remaining elements.
• Return Result: Return the subsequence constructed so far.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def minSubsequence(self, nums: List[int]) -> List[int]:
        nums.sort(reverse=True) # Sort the array in non-increasing order
        total_sum = sum(nums)
        current_sum = 0

        result = [] # To store the result

        for num in nums:
            current_sum += num
            result.append(num)
            if current_sum > total_sum / 2:
                break

        return result

Explanation

• Sorting the array ensures that we consider the largest elements first, so we can obtain a subsequence with the minimum size.
• By keeping track of the current_sum, we can stop as soon as we have a subsequence whose sum is strictly greater than the sum of the other elements.

Example

For the input nums = [4,3,10,9,8], the sorted array will be [10,9,8,4,3]. The resulting subsequence will be [10,9], which has a sum strictly greater than the sum of the remaining elements.

This solution meets the constraints and efficiently computes the required output by sorting the array once and then iterating through it.