양의 정수 배열이 주어지면 작업은 모든 고유 요소를 포함하는 하위 배열을 지우는 것입니다. 하위 배열을 지워서 얻는 것은 해당 요소의 합과 같습니다.
현재 하위 배열의 앞이나 뒤에 있는 항을 지워서 현재 하위 배열의 최대 합계를 반환합니다. 정확히 하나의 하위 배열을 지워서 최대 합계를 얻을 수 있습니다.
배열 arr a의 하위 배열로 호출됩니다. a의 연속적인 하위 시퀀스를 형성하는 경우 즉, 일부 (l,r)에 대해 [l], a[l+1],..., a[r]과 같은 경우입니다. 예를 들어,
입력-1 -
arr[ ] = { 1,2,4,5,6 } 출력 -
17
설명 − 최적의 하위 배열은 {2,4,5,6}입니다.
입력-2 -
arr[ ]= {5,3,1,3,5,3,1,3,5} 출력 -
9
설명 − 최적의 하위 배열은 {5,3,1} 또는 {1,3,5}입니다.
이 문제를 해결하기 위한 접근 방식
이 문제를 해결하기 위해 슬라이딩 창 개념을 사용합니다. 이 기술은 중첩 루프를 단일 루프로 변환하여 시간 복잡성을 줄이는 방법을 보여줍니다.
이 기술에서는 먼저 (왼쪽 및 오른쪽)에 대한 두 개의 포인터와 창 크기를 'win'으로 초기화합니다. 배열을 반복하는 동안 특정 승리의 크기가 최대인지 여부를 확인합니다. 최대값을 찾으면 출력으로 반환합니다.
이 문제를 해결하기 위한 접근 방식,
-
양의 정수 배열을 입력합니다.
-
정수 함수 maximumUniqueSubarray(vector&arr)는 배열을 입력으로 사용합니다.
-
세 포인터 'I', 'j' 및 창 크기 'win'을 취하고 배열을 반복하고 요소가 있는 현재 창이 HashSet에 있는지 확인한 다음 창을 이동하고 다른 요소를 다시 확인합니다. 존재하지 않으면 HashSet에 삽입하고 이전 요소를 제거하는 창 크기를 줄입니다.
-
결과와 창 값에서 최대값을 찾습니다.
-
결과를 반환합니다.
예시
#include<bits/stdc++.h>
using namespace std;
int maximumUniqueSubarray(vector<int>& arr) {
int result = 0;
unordered_set<int> hashset;
for (int i = 0, j = 0, win = 0; j < arr.size(); j++) {
while (hashset.find(arr[j]) != hashset.end()) {
hashset.erase(arr[i]);
win -= arr[i];
i++;
}
hashset.insert(arr[j]);
win += arr[j];
result = max(result, win);
}
return result;
}
int main(){
vector<int>nums;
nums<<5,3,1,3,5,3,1,3,5;
cout<<maximumUniqueSubarray(nums)<<endl;
return 0;
} 출력
위의 코드를 실행하면 다음과 같이 출력이 생성됩니다.
9