최대 연속 수의 부분 집합

제목:
정수 배열 에 가장 많은 연속 수 를 포함 하 는 부분 집합 을 찾 습 니 다. 예 를 들 어 15, 7, 12, 6, 14, 13, 9, 11 을 주면 5: [11, 12, 13, 14, 15] 로 돌아 갑 니 다.가장 쉬 운 방법 은 sort 다음 에 한 번 스 캔 하 는 것 입 니 다. 그런데 o (nlgn) 를 원 합 니 다. O (n) 방법 이 있 습 니까?
분석:
우 리 는 먼저 집합 이라는 데이터 구 조 를 배 웁 니 다.
그리고 집합 (Disjoint set 또는 Union - find set) 은 간단 하고 용도 가 광범 위 한 알고리즘 과 데이터 구조 이다.그리고 조사 집 은 몇 개의 교차 하지 않 는 집합 으로 비교적 빠 른 합병 과 요소 가 있 는 집합 을 판단 하 는 작업 을 실현 할 수 있 고 응용 이 많다. 예 를 들 어 그림 이 없 는 연결 분량 의 갯 수 등 이다.
그리고 조사 집 은 다음 과 같은 세 가지 조작 을 편리 하 게 할 수 있다.
1、Make_Set (x) 모든 요 소 를 하나의 집합 으로 초기 화 합 니 다.
초기 화 된 후에 모든 요소 의 아버지 노드 는 그 자체 이 고 모든 요소 의 조상 노드 도 그 자체 이다 (상황 에 따라 변 할 수도 있다).
2、Find_Set (x) 요소 가 있 는 집합 찾기
원소 가 있 는 집합 을 찾 는데 그 정 수 는 이 원소 가 있 는 집합 을 찾 은 조상 이다.이것 이 야 말로 판단 과 합병 의 최종 근 거 를 수집 하 는 것 이다.
두 원소 가 같은 집합 에 속 하 는 지 아 닌 지 를 판단 하고 그들 이 모인 조상 이 같은 지 를 보면 된다.
두 집합 을 합 친 것 도 한 집합 조상 을 다른 집합 조상 으로 만 드 는 것 으로 구체 적 으로 설명 도 를 볼 수 있다.
3. Union (x, y) 합병 x, y 가 있 는 두 개의 집합
두 개의 교차 하지 않 는 집합 을 합병 하 는 것 은 매우 간단 하 다.
Find 이용셋 은 두 집합 조상 을 찾 아 한 집합 조상 을 다른 집합 조상 에 게 가 리 켰 다.그림 과 같다
그리고 집합 최적화:
1、Find_설정 (x) 시 경로 압축
조상 을 찾 을 때 우 리 는 일반적으로 재 귀적 으로 찾 지만 요소 가 많 거나 나무 전체 가 하나의 사슬 로 변 할 때 매번 FindSet (x) 는 모두 O (n) 의 복잡 도 입 니 다. 이 복잡 도 를 줄 일 방법 이 있 습 니까?
답 은 긍정 적 이다. 이것 이 바로 경로 압축 이다. 즉, 우리 가 '전달' 을 통 해 조상 노드 를 찾 은 후에 '역 추적' 을 할 때 그의 자손 노드 를 조상 에 게 직접 가리 키 는 것 이다. 그러면 나중에 다시 FindSet (x) 시 복잡 도 는 O (1) 가 됩 니 다. 다음 그림 과 같 습 니 다.이 를 통 해 알 수 있 듯 이 경로 압축 은 이후 의 찾기 에 편리 하 다.
2. 유 니 온 (x, y) 시 순서대로 합병
즉, 합 칠 때 요소 가 적은 집합 을 요소 가 많은 집합 에 합 쳐 합 친 후에 나무의 높이 가 상대 적 으로 작 을 것 이다.
배경 지식 이 생기 면 우 리 는 그것 을 어떻게 이용 하여 이 문 제 를 해결 하 는 지 보 자.
우선, MakeSet (x) 는 모든 요 소 를 하나 로 바 꾸 고 집합 을 검사 한 다음 에 Union (x - 1, x), Union (x, x + 1) 을 스 캔 합 니 다.
다음 문 제 는 x - 1, x + 1 의 위 치 를 어떻게 빨리 찾 느 냐 하 는 것 이다.상수 복잡 도 를 찾 는 해시 표를 도입 해 야 한다.

#include 
#include
using namespace std;

const int MAX = 100;
int Father[MAX];
int Rank[MAX];

void MakeSet(int x){
	Father[x] = x;
	Rank[x] = 1;
}

int FindFather(int x){
	if(x != Father[x])
		Father[x] = FindFather(Father[x]);
	return Father[x];
}

void Union(int x, int y){
	int a = FindFather(x);
	int b = FindFather(y);
	if(a == b)
		return;
	else{
		int ar = Rank[a];
		int br = Rank[b];
		if(ar <= br){
			Father[a] = b;
			Rank[b] += Rank[a];
		}else{
			Father[b] = a;
			Rank[a] += Rank[b];
		}
	}
}

int main()
{
	const int length = 15;
	int arr[length] = {15, 7, 12, 6, 14, 13, 10, 11, 4, 5, 8, 3, 2, 16, 17};
	hash_map ihmap;
	for(int i = 0; i < length; ++i)
	{
		MakeSet(i);
		ihmap[arr[i]]=i;
	}

	for(int i = 0; i < length; ++i)
	{
		hash_map::iterator tmp;
		tmp = ihmap.find(arr[i]-1);
		if(tmp != ihmap.end())
		{
			Union(i,tmp->second);			
		}
		tmp = ihmap.find(arr[i]+1);
		if(tmp != ihmap.end())
		{
			Union(i,tmp->second);			
		}
	}
	int max = Rank[0];
	int father = 0;
	for(int i = 1; i< length; ++i)
		if(Rank[i]>max){
			max = Rank[i];
			father = i;
		}
	cout<