1695. Maximum Erasure Value

문제

https://leetcode.com/problems/maximum-erasure-value/description/

풀이

class Solution {
    public int maximumUniqueSubarray(int[] nums) {
        int answer = 0;
        Map<Integer, Integer> map = new HashMap<>();
        int lt = 0;
        int sum = 0;
        
        for(int rt = 0; rt < nums.length; rt++) {
            sum += nums[rt];
            map.put(nums[rt], map.getOrDefault(nums[rt], 0) + 1);
            while(map.get(nums[rt]) > 1) {
                map.put(nums[lt], map.get(nums[lt]) - 1);
                sum -= nums[lt];
                lt++;
            }
            answer = Math.max(answer, sum);
        }

        return answer;
        
    }
}

• 최대합을 가진 unique한 원소로 이루어진 subarray 구하기
• 중복이 존재하는지 확인만 하면 되므로, Set으로도 풀 수 있다. (더 빠름)

class Solution {
    public int maximumUniqueSubarray(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int lt = 0;
        int answer = 0;
        int sum = 0;

        for(int rt = 0; rt < nums.length; rt++) {
            sum += nums[rt];
            while(set.contains(nums[rt])) {
                set.remove(nums[lt]);
                sum -= nums[lt];
                lt++;
            }
            set.add(nums[rt]);
            answer = Math.max(sum, answer);
        }

        return answer;

    }
}