[LeetCode] 1695. Maximum Erasure Value

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

Maximum Erasure Value - LeetCode

Maximum Erasure Value

 

int 배열이 있을때,

unique elements로만 구성된 이어져있는 subarray들의 합 중 가장 큰 걸 출력한다.

투 포인터를 이용하여 풀었다.

 

100000개의 수가 subarray에 들어있는지 여부를 체크하는 배열을 하나 만들고,

투포인터를 이용해, 오른쪽 포인터의 다음 수가 subarray에 이미 있을경우엔 

왼쪽 포인터를 증가, 없을 경우엔 오른쪽 포인터를 증가시켰다.

또한 왼쪽과 오른쪽이 같을 경우엔 무조건 오른쪽을 증가시켜줬다.

그러면서 최대값을 관리하였다.

 

전체코드는 아래와 같다.

 

class Solution {
public:
    int maximumUniqueSubarray(vector<int>& nums) {
        int chk[100005];
        for (int i=0; i<=100000; i++) chk[i]=0;
        int l=0, r=0, M=nums[0], sum = nums[0];
        chk[nums[0]] = 1;
        while(r<nums.size()-1) {
            if (!chk[nums[r+1]] || l==r) {
                chk[nums[++r]]++;
                sum+=nums[r];
                M = max(M,sum);
            } else {
                sum-=nums[l];
                chk[nums[l++]]--;
            }
        }
        return M;        
    }
};