Code Logo

Minimum Subsequence in Non-Increasing Order

Published at24 Jul 2026
Created by
Easy 0 views
Like0

Given an array nums, find a subsequence (not necessarily contiguous) such that the sum of its elements is strictly greater than the sum of the remaining elements, and the subsequence has the minimum possible length. If multiple such subsequences exist, return the one with the largest sum (or equivalently, the one with the largest elements). Return the subsequence sorted in non-increasing order.

Sort the array in descending order. Compute the total sum. Greedily take the largest elements until the accumulated sum exceeds half of the total sum. Since we take the largest elements first, this minimizes the subsequence length.

Time is O(n log n) for sorting plus O(n) for the greedy accumulation. Space is O(n) for the result.

Edge cases include all positive numbers, mixed signs, and single element arrays.

Taking the largest elements first guarantees the subsequence with minimum length because fewer large elements are needed to exceed half the total sum. Sorting descending and accumulating until the condition is met produces the required result.

The result is always sorted in non-increasing order because we take elements from largest to smallest. This ensures the subsequence has the maximum possible sum for the minimum length, satisfying both the sum and length optimization criteria.

Example Input & Output

Example 1
Input
[10,2,5]
Output
[10]
Explanation

10 > 2+5=7.

Example 2
Input
[1,2,3]
Output
[3,2]
Explanation

3+2=5 > 1.

Example 3
Input
[4,4,7,6,7]
Output
[7,7,6]
Explanation

7+7+6=20 > 4+4=8.

Example 4
Input
[4,3,10,9,8]
Output
[10,9]
Explanation

10+9=19 > 4+3+8=15.

Example 5
Input
[6]
Output
[6]
Explanation

Single element trivially satisfies.

Algorithm Flow

Recommendation Algorithm Flow for Minimum Subsequence in Non-Increasing Order
Recommendation Algorithm Flow for Minimum Subsequence in Non-Increasing Order

Solution Approach

Sort descending, accumulate until sum > total/2. Return taken elements.

function solution(nums) {
  nums.sort(function(a,b){return b-a;});
  var total = 0;
  for (var i = 0; i < nums.length; i++) total += nums[i];
  var sum = 0;
  var result = [];
  for (var i = 0; i < nums.length; i++) {
    sum += nums[i];
    result.push(nums[i]);
    if (sum > total - sum) break;
  }
  return result;
}

Time O(n log n), Space O(n).

Best Answers

java
import java.util.*;
class Solution {
    public List<Integer> solution(int[] nums) {
        Arrays.sort(nums);
        List<Integer> res=new ArrayList<>();
        int total=0;for(int n:nums)total+=n;
        int acc=0;
        for(int i=nums.length-1;i>=0;i--){
            acc+=nums[i];res.add(nums[i]);
            if(acc>total-acc) break;
        }
        return res;
    }
}