HomeAboutMeBlogGuest
© 2025 Sejin Cha. All rights reserved.
Built with Next.js, deployed on Vercel
👻
개발 기록/
코딩테스트 스터디
코딩테스트 스터디/
Maximum Erasure Value

Maximum Erasure Value

Link
https://leetcode.com/problems/maximum-erasure-value/
Deadline
Jun 19, 2022
Status
Archived
Type
Array
Hash Table
You are given an array of positive integers nums and want to erase a subarray containing unique elements. The score you get by erasing the subarray is equal to the sum of its elements.
Return the maximum score you can get by erasing exactly one subarray.
An array b is called to be a subarray of a if it forms a contiguous subsequence of a, that is, if it is equal to a[l],a[l+1],...,a[r] for some (l,r).
Example 1:
Example 2:
Constraints:
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 104

풀이

은찬
재영

설명

투포인터로 풀면 더욱 간단한 문제입니다!

이유

결국 고유한 값들을 연속으로 갖고 있는 집합 중 가장 긴 것을 찾아야 하는 문제입니다.
 
이는 포인터가 없을 경우 반복문을 최소 2개 이상 사용해야 합니다.
  1. 맨 처음 반복문을 돌린다.
  1. 이때 가능한 집합의 조건에 맞춰 구간 배열을 또 다시 반복문을 돌린다.
따라서 최악의 경우엔 O(N^2)의 연산이 드는데요.
 
투 포인터의 경우에는 left와 right를 설정해주어, 배열을 다시 정하는 반복적인 로직을 더욱 간단하게 반복문 하나로 처리할 수 있습니다. 따라서 투 포인터로 해결하였습니다.
 
효성
시간 초과…
참고한 풀이
Input: nums = [4,2,4,5,6]
Output: 17
Explanation: The optimal subarray here is [2,4,5,6].

Input: nums = [5,2,1,2,5,2,1,2,5]
Output: 8
Explanation: The optimal subarray here is [5,2,1] or [1,2,5].

var maximumUniqueSubarray = function(nums) {
    let answer = 0;
    let current = 0;
    const obj = {};
    
    for(let left = 0, right = 0; right < nums.length; right++){
        while(obj[nums[right]]){
            current -= nums[left];
            delete obj[nums[left++]];
        }
        
        obj[nums[right]] = true;
        current += nums[right];
        answer = Math.max(answer, current);
    }
    
    return answer;
};
const maximumUniqueSubarray = (nums) => {
  let result = 0;

  let left = 0;
  let right = 0;

  let total = 0;
  let set = new Set();

  while (left <= right && right !== nums.length) {
    const head = nums[left];
    const next = nums[right];

    if (!set.has(next)) {
      right += 1;

      set.add(next);
      total += next;

      result = Math.max(result, total);
    } else {
      left += 1;

      set.delete(head);
      total -= head;
    }
  }
  return Math.max(result, total);
};
var maximumUniqueSubarray = function(nums) {
    const map = new Map();
    const answer = [];
    const len = nums.length;
    let i = 0;
    let cnt = 0;
    
    while(i < len) {
        if(map.has(nums[i])) {
            answer.push(cnt);
            cnt = 0;
            i = map.get(nums[i]) + 1;
            map.clear();
        }
        map.set(nums[i], i);
        cnt += nums[i];
        i++;
    }
    
    answer.push(cnt);
    
    return Math.max(...answer);
};
var maximumUniqueSubarray = function(nums) {
    const set = new Set();
    let len = nums.length;
    let j = 0;
    let i = 0;
    let sum = 0;
    let res = 0;

    while(j < len && i < len){
        if(set.has(nums[j])){
            sum -= nums[i];
            set.delete(nums[i]);
            i++;
        }
        else{
            sum += nums[j];
            res = Math.max(sum, res);
            set.add(nums[j]);
            j++;
        }
    }
    
    return res;
};