[JAVA 문제 풀이] 402. Maximum Unique Subarray Sum After Deletion

Maximum Unique Subarray Sum After Deletion - LeetCode

Can you solve this real interview question? Maximum Unique Subarray Sum After Deletion - You are given an integer array nums. You are allowed to delete any number of elements from nums without making it empty. After performing the deletions, select a subarray of nums such that: 1. All elements in the subarray are unique. 2. The sum of the elements in the subarray is maximized. Return the maximum sum of such a subarray.   Example 1: Input: nums = [1,2,3,4,5] Output: 15 Explanation: Select the entire array without deleting any element to obtain the maximum sum. Example 2: Input: nums = [1,1,0,1,1] Output: 1 Explanation: Delete the element nums[0] == 1, nums[1] == 1, nums[2] == 0, and nums[3] == 1. Select the entire array [1] to obtain the maximum sum. Example 3: Input: nums = [1,2,-1,-2,1,0,-1] Output: 3 Explanation: Delete the elements nums[2] == -1 and nums[3] == -2, and select the subarray [2, 1] from [1, 2, 1, 0, -1] to obtain the maximum sum.   Constraints: * 1 <= nums.length <= 100 * -100 <= nums[i] <= 100

https://leetcode.com/problems/maximum-unique-subarray-sum-after-deletion/description

정수 배열 'nums'가 주어집니다.

'nums'에서 빈 요소 없이 모든 요소를 삭제할 수 있습니다.
삭제를 수행한 후에는 'nums'의 하위 배열을 선택하여 다음과 같이 할 수 있습니다:

1. 하위 배열의 모든 요소는 고유합니다. >> 중복된 값을 가질 수 없음
2. 하위 배열의 요소들의 합이 최대화됩니다.

이러한 하위 배열의 최대 합을 반환합니다.

제약 조건:
* 1 <= nums.length <= 100
* -100 <= nums [i] <= 100

내가 작성한 코드

import java.util.*;

class Solution {
    public int maxSum(int[] nums) {
        TreeSet<Integer> set = new TreeSet<>(); // treeset 으로 중복 제거 + 오름차순 정렬
    
        for (int num : nums) {
            set.add(num);
        }

        // 숫자가 1개만 있는 경우
        if(set.size() == 1) {
            return nums[0];
        }

        int min = Integer.MIN_VALUE; // 음수만 있는 경우 대비
        int answer = 0; // 양수들의 합

        while(set.size() > 0) {
            int num = set.pollFirst(); // 숫자를 set에서 꺼내면서 제거

            // 숫자가 0이하인 경우
            if (num <= 0) {
                min = Math.max(min, num); // min 업데이트
                continue;
            }

            // 양수들은 더하기
            answer += num;
        }

        // min이 업데이트가 안됨 >> answer 반환
        // min이 업데이트가 되었음 >> answer가 0이 아닌 경우 answer 반환 >> 0이면 min 반환
        return min == Integer.MIN_VALUE ? answer : (answer != 0 ? answer : min);
    }
}

다른 사람의 코드

import java.util.*;

class Solution {
    public int maxSum(int[] nums) {
        Arrays.sort(nums); // 오름차순 정렬

        int prev = nums[nums.length - 1]; // 최대값
        int sum = prev; // 최대값 더해두기

        // 역순으로 순회
        for (int i = nums.length - 2; i >= 0; i--) {
            int n = nums[i]; // 이전 수

            // 음수일 경우
            if (n <= 0) {
                return sum; // 바로 반환
            } else if (n != prev) { // 현재 수와 이전수가 다를 때만 숫자 더하기
                sum = sum + n;
            }

            prev = n; // 이전 수 업데이트
        }

        return sum;
    }
}