Chúng ta được cung cấp với một mảng N số với các phần tử nằm trong phạm vi 0 và N-1. Các phần tử không được sắp xếp. Mục đích là tìm số lượng phân vùng tối đa của mảng có thể được sắp xếp riêng lẻ và sau đó có thể được nối với nhau để tạo thành một mảng được sắp xếp toàn bộ có độ dài N.
Mỗi phân vùng được chọn sao cho các phần tử trong đó không được sắp xếp. Đối với N số nằm trong khoảng từ 0 đến N-1, các phần tử được sắp xếp có chỉ số bằng giá trị. Arr [i] =i.
Chúng tôi sẽ giải quyết vấn đề này bằng cách so sánh từng phần tử với giá trị lớn nhất được tìm thấy cho đến nay ở bên trái của nó. Khi đạt đến đúng vị trí tối đa, (tối đa ==i). Tất cả các phần tử bên trái của nó đều ít hơn nên có thể tạo một phân vùng riêng biệt. Tất cả ở bên phải của nó là lớn hơn. Bây giờ, hãy thực hiện quy trình tương tự cho phần còn lại của các phần tử bên phải và chia chúng thành các phân vùng.
Hãy cùng hiểu với các ví dụ.
Đầu vào - Arr [] ={0,3,2,1,4,5}
Đầu ra - Số lượng phân vùng tối đa - 3
Giải thích - Bắt đầu từ 0, Cho max =0 Arr [0]
Giữa chỉ số 0 và 3. 3 là tối đa. Khi đạt đến chỉ số i =3 (maxx ==i). Vì vậy, phân vùng đầu tiên là [0,3,2,1]
Đối với chỉ số 4, tối đa là 4. Chỉ số i =4 (maxx ==i). Vì vậy, phân vùng thứ hai là [4]
Đối với chỉ số 5, tối đa là 5. Chỉ số i =5 (maxx ==i). Vì vậy, phân vùng thứ hai là [5]
Tổng 3 phân vùng [0,3,2,1] [4] [5]. Sắp xếp từng thứ và nối.
Đầu vào - Arr [] ={5,4,3,2,1,0}
Đầu ra - Số lượng phân vùng tối đa - 1
Giải thích - Bắt đầu từ 0, Cho max =0 Arr [0]
Giữa chỉ số 0 và 5. 5 là tối đa. Khi đạt đến chỉ số i =5 (maxx ==i). Vì vậy, chỉ phân vùng là [5,4,3,2,1,0]
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Chúng tôi lấy một mảng số nguyên Num [] được khởi tạo với các số trong phạm vi từ 0 đến N.
-
Các phân vùng hàm (int arr [], int n) nhận một mảng và độ dài của nó làm tham số và trả về số lượng các phân vùng tối đa có thể được sắp xếp riêng lẻ để sắp xếp toàn bộ mảng.
-
Số lượng phân vùng ban đầu là 0. Giá trị lớn nhất ban đầu tính bằng maxx là arr [0].
-
Đối với tất cả các phần tử bắt đầu từ phần tử ngoài cùng bên trái. Tìm xem nó có lớn hơn maxx không.
-
Nếu arr [i]> maxx là true. Cập nhật maxx.
-
Nếu maxx và chỉ mục hiện tại giống nhau. (maxx ==i) thì tất cả các phần tử cho đến tôi là một phần của một phân vùng. Số lượng tăng dần.
-
Làm điều này cho các phần tử còn lại ở bên phải cho đến hết.
-
Trả về kết quả là số đếm.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Maximum partitions that can be sorted: 18