Portfolio

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:


Input: nums = [4,2,4,5,6]
Output: 17
Explanation: The optimal subarray here is [2,4,5,6].

Example 2:


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].

Constraints:

1 <= nums.length <= 105

1 <= nums[i] <= 104

풀이

은찬


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;
};

재영

설명

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

이유

결국 고유한 값들을 연속으로 갖고 있는 집합 중 가장 긴 것을 찾아야 하는 문제입니다.

이는 포인터가 없을 경우 반복문을 최소 2개 이상 사용해야 합니다.

맨 처음 반복문을 돌린다.

이때 가능한 집합의 조건에 맞춰 구간 배열을 또 다시 반복문을 돌린다.

따라서 최악의 경우엔 O(N^2)의 연산이 드는데요.

투 포인터의 경우에는 left와 right를 설정해주어, 배열을 다시 정하는 반복적인 로직을 더욱 간단하게 반복문 하나로 처리할 수 있습니다. 따라서 투 포인터로 해결하였습니다.


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;
};

Maximum Erasure Value

풀이

설명

이유