0과 N-1 범위에 있는 요소가 있는 N개의 숫자 배열이 제공됩니다. 요소가 정렬되지 않습니다. 목표는 개별적으로 정렬할 수 있는 배열의 최대 파티션 수를 찾은 다음 연결하여 길이가 N인 전체 정렬된 배열을 만드는 것입니다.
각 파티션은 그 안의 요소가 정렬되지 않도록 선택됩니다. 0과 N-1 사이의 N 숫자의 경우 정렬된 요소는 값과 동일한 인덱스에 있습니다. Arr[i] =i.
각 요소를 왼쪽에서 지금까지 찾은 최대값과 비교하여 이 문제를 해결할 것입니다. 최대값의 올바른 위치에 도달하면 (최대값 ==i ). 왼쪽에 있는 모든 요소가 작아서 별도의 파티션을 만들 수 있습니다. 오른쪽에 있는 모든 것이 더 큽니다. 이제 나머지 올바른 요소에 대해 동일한 절차를 수행하고 파티션으로 나눕니다.
예를 들어 이해합시다.
입력 - Arr[]={ 0,3,2,1,4,5 }
출력 − 최대 파티션 수 − 3
설명 − 0부터 시작하여 max=0 Arr[0]
로 설정합니다.인덱스 0과 3 사이. 3이 최대입니다. 인덱스 i=3( maxx==i)에 도달했을 때. 따라서 첫 번째 파티션은 [0,3,2,1]
입니다.인덱스 4의 경우 최대값은 4입니다. 인덱스 i=4( maxx==i). 따라서 두 번째 파티션은 [4]
입니다.인덱스 5의 경우 최대값은 5입니다. 인덱스 i=5( maxx==i). 따라서 두 번째 파티션은 [5]
입니다.총 3개의 파티션 [0,3,2,1][4][5]. 각각을 정렬하고 연결합니다.
입력 - Arr[]={ 5,4,3,2,1,0 }
출력 − 최대 파티션 수 − 1
설명 − 0부터 시작하여 max=0 Arr[0]
로 설정합니다.인덱스 0과 5 사이. 5가 최대입니다. 인덱스 i=5( maxx==i)에 도달했을 때. 따라서 파티션만 [5,4,3,2,1,0]
입니다.아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
0에서 N 범위의 숫자로 초기화된 정수 배열 Num[]을 사용합니다.
-
partitions(int arr[], int n ) 함수는 배열과 그 길이를 매개변수로 취하고 전체 배열을 정렬하기 위해 개별적으로 정렬할 수 있는 최대 파티션 수를 반환합니다.
-
초기 파티션 수는 0입니다. 초기 최대값은 maxx에서 arr[0]입니다.
-
가장 왼쪽 요소에서 시작하는 모든 요소에 대해. maxx보다 큰지 찾으십시오.
-
arr[i]>maxx가 참인 경우. 최대 업데이트
-
현재 maxx와 index가 같은 경우. ( maxx==i ) 그러면 i까지의 모든 요소는 하나의 파티션의 일부입니다. 증분 수.
-
오른쪽에 있는 나머지 요소에 대해 끝까지 이 작업을 수행합니다.
-
결과를 count로 반환합니다.
예시
#include <bits/stdc++.h>
using namespace std;
int partitions(int arr[], int n){
int count = 0;
int maxx = arr[0];
for (int i = 0; i < n; ++i) {
if(arr[i] > maxx)
maxx=arr[i];
if (maxx == i)
count++;
}
return count;
}
int main(){
int Num[] = { 2,1,0,4,5,3 };
int len = 6;
cout <<"Maximum partitions that can be sorted: "<<partitions(Num, len);
return 0;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Maximum partitions that can be sorted: 18