Problem: Minimum Subsequence in Non-Increasing Order

The problem asks to find the minimum-sized subsequence from a given array nums such that the sum of its elements is strictly greater than the sum of the remaining elements. If multiple such subsequences exist, the one with the maximum total sum should be returned. The subsequence must be sorted in non-increasing order.

Solution Approach: Greedy with Sorting

The optimal solution utilizes a greedy approach combined with sorting. The steps are as follows:

1. Sort: Sort the input array nums in descending order. This ensures that we consider the largest elements first, maximizing the sum of the subsequence while minimizing its size.

2. Iterate and Accumulate: Iterate through the sorted array. Maintain two variables:

   • total_sum: The sum of all elements in the input array.
   • current_sum: The sum of elements in the currently selected subsequence.

3. Subsequence Selection: In each iteration, add the current element to the subsequence (current_sum) and check the condition current_sum > total_sum - current_sum. This condition efficiently checks if the sum of the selected subsequence exceeds the sum of the remaining elements.

4. Termination Condition: If the condition current_sum > total_sum - current_sum is met, the subsequence selection is complete, and the current subsequence is the solution.

Time and Space Complexity Analysis

• Time Complexity: The dominant operation is sorting the array, which takes O(n log n) time using efficient sorting algorithms like merge sort or quicksort. The subsequent iteration takes linear time, O(n). Therefore, the overall time complexity is O(n log n).

• Space Complexity: Sorting in-place algorithms can be used (like merge sort variants or optimized quicksort) so the space complexity of sorting is O(log n) in the average case due to the recursion stack and O(n) in the worst-case for quicksort if the pivot selection is very poor. Creating the subsequence requires O(n) space in the worst case (if the entire array forms the subsequence), so overall space complexity is O(n).

Code Implementation in Multiple Languages

The code implementations below follow the described approach:

Python:

def minSubsequence(nums):
    nums.sort(reverse=True)  # Sort in descending order
    total_sum = sum(nums)
    current_sum = 0
    result = []
    for num in nums:
        current_sum += num
        result.append(num)
        if current_sum > total_sum - current_sum:
            break
    return result

Java:

import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;
 
class Solution {
    public List<Integer> minSubsequence(int[] nums) {
        Arrays.sort(nums); //Sort in descending order
        int n = nums.length;
        for(int i = 0; i < n / 2; i++){
            int temp = nums[i];
            nums[i] = nums[n - 1 - i];
            nums[n - 1 - i] = temp;
        }
        int total_sum = 0;
        for(int num : nums){
            total_sum += num;
        }
        int current_sum = 0;
        List<Integer> result = new ArrayList<>();
        for (int num : nums) {
            current_sum += num;
            result.add(num);
            if (current_sum > total_sum - current_sum) {
                break;
            }
        }
        return result;
    }
}

C++:

#include <vector>
#include <numeric>
#include <algorithm>
 
class Solution {
public:
    std::vector<int> minSubsequence(std::vector<int>& nums) {
        std::sort(nums.rbegin(), nums.rend()); //Sort in descending order
        int total_sum = std::accumulate(nums.begin(), nums.end(), 0);
        int current_sum = 0;
        std::vector<int> result;
        for (int num : nums) {
            current_sum += num;
            result.push_back(num);
            if (current_sum > total_sum - current_sum) {
                break;
            }
        }
        return result;
    }
};

JavaScript:

const minSubsequence = (nums) => {
    nums.sort((a, b) => b - a); // Sort in descending order
    const totalSum = nums.reduce((sum, num) => sum + num, 0);
    let currentSum = 0;
    const result = [];
    for (const num of nums) {
        currentSum += num;
        result.push(num);
        if (currentSum > totalSum - currentSum) {
            break;
        }
    }
    return result;
};

These code examples demonstrate the solution in different languages, all following the same efficient greedy algorithm. Remember that the specific implementation details might vary slightly depending on the language's standard library functions and conventions.