문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

배열 nums가 주어졌을 때, 배열의 부분 중에 그 부분에 포함되지 않은 요소들의 합보다 모든 요소의 합이 더 큰 부분을 구해라.

만약 답이 여러 개라면, 크기가 가장 작은 부분을 반환하고, 그래도 여러 개라면 모든 요소의 합이 가장 큰 부분을 반환해라. 배열의 부분은 배열에서 일부 요소(없어도 됨)를 제거하여 얻을 수 있다.

Example

#1
Input: nums = [4, 3, 10, 9, 8]
Output: [10, 9]
Explanation: 부분 수열 [10, 9], [10, 8]은 그 요소들의 합이 포함되지 않은 요소들의 합보다 큰 부분 수열이다. 그러나 부분 수열 [10, 9]는 요소들의 합이 최대이다.

#2
Input: nums = [4, 4, 7, 6, 7]
Output: [7, 7, 6]

Constraints

• 1 <= nums.length <= 500
• 1 <= nums[i] <= 100

Solved

class Solution {
    public List<Integer> minSubsequence(int[] nums) {
        List<Integer> result = new ArrayList<>();

        Arrays.sort(nums);

        int totalSum = 0;

        for(int num : nums){
            totalSum += num;
        }

        int sum = 0;

        for(int i = nums.length - 1; i >= 0; i--){
            totalSum -= nums[i];
            sum += nums[i];
            result.add(nums[i]);

            if(sum > totalSum){
                return result;
            }
        }

        return result;
    }
}