최대 길이를 갖는 하위 배열의 길이를 찾는 작업을 갖는 N 정수 배열을 제공했다고 가정합니다. 길이가 최대이거나 합이 0인 부분배열이 없으면 '0'을 반환합니다. 예를 들어,
입력-1 -
N = 8
A[ ] = {15, -5, -1, 5,1, 4 } 출력 -
4
설명 − 제로섬이 있는 가장 큰 부분배열은 { -5, -1, 5, 1}이며 길이는 4입니다.
입력-2 -
N = 5
A[ ] = {3, 2 ,4, 8, -1} 출력 -
0
설명 − 합이 0인 하위 배열이 존재하지 않으므로 출력은 '0'입니다.
이 문제를 해결하기 위한 접근 방식
이 특정 문제를 해결하기 위한 몇 가지 접근 방식이 있습니다. 선형 시간 O(n)에 가장 적합한 알고리즘은 해시 테이블을 사용하는 것입니다.
아이디어는 합계가 키로 저장되고 인덱스가 값으로 저장되는 모든 하위 배열의 합계를 저장하는 해시 테이블을 만드는 것입니다.
먼저 전체 배열을 탐색하고 현재 합계를 저장합니다. 현재 합계가 해시 테이블에서 사용 가능한지 여부를 확인합니다. 해시 테이블에 있는 경우 하위 배열의 최대 길이를 업데이트합니다.
-
배열의 N 크기를 입력합니다.
-
lenMax(int *arr, int size) 함수는 배열과 그 크기를 입력으로 받아 합계 0을 포함하는 하위 배열의 최대 길이를 반환합니다.
-
키를 합계로, 값을 인덱스로 포함하는 정수의 정렬되지 않은 맵은 합계가 반복되는지 여부를 확인합니다.
-
배열 요소를 반복하고 합계가 해시 테이블에 있는 경우 배열의 현재 합계를 찾은 다음 하위 배열의 최대 길이를 찾습니다. 그렇지 않은 경우 새 합계와 해당 인덱스를 사용하여 해시 테이블에 삽입합니다.
-
최대 길이를 출력으로 반환합니다.
예시
#include<bits/stdc++.h>
using namespace std;
int lenMax(int *arr, int size){
unordered_map<int,int>mp;
int sum=0;
int maxlen=0;
for(int i=0;i<size;i++){
sum+=arr[i];
if(arr[i]==0 && maxlen==0){
maxlen=1;
}
if(sum==0){
maxlen=i+1;
}
if(mp.find(sum)!= mp.end()){
maxlen= max(maxlen, i-mp[sum]);
} else {
mp[sum]=i;
}
}
return maxlen;
}
int main(){
int N=6;
int A[N]={15,-2,2,-8,1,7,10,23};
cout<<lenMax(A,N)<<endl;
return 0;
} 출력
위의 코드를 실행하면 출력이 다음과 같이 인쇄됩니다.
5
sum=0인 가장 큰 부분배열은 {-2, 2, -8, 1, 7}입니다. 따라서 가장 큰 부분배열의 길이는 '5'가 됩니다.