Số phân vùng tối đa để sắp xếp riêng rồi nối thành mảng đã sắp xếp C++

Cho mảng N phần tử chứa các số từ 0 đến N-1 (hoán vị). Tìm số phân vùng tối đa sao cho: sắp xếp riêng từng phân vùng rồi nối lại được mảng hoàn toàn sắp xếp.

Ví dụ minh họa

Ví dụ 1:

• Input: Arr = {0, 3, 2, 1, 4, 5}
• Output: 3
• Giải thích: Phân vùng: [0,3,2,1], [4], [5]. Sắp xếp từng phần: [0,1,2,3], [4], [5] → nối thành [0,1,2,3,4,5].

Ví dụ 2:

• Input: Arr = {5, 4, 3, 2, 1, 0}
• Output: 1
• Giải thích: Chỉ có 1 phân vùng là cả mảng.

Quan sát quan trọng

Với hoán vị 0..N-1, mảng đã sắp xếp là arr[i] = i. Một phân vùng kết thúc tại chỉ số i nếu và chỉ nếu max(arr[0..i]) = i. Lúc này tất cả phần tử ≤ i đã nằm trong phân vùng này.

Mã nguồn C++

#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 << "So phan vuong toi da: " << partitions(Num, len);
    return 0;
}

Kết quả chạy chương trình

So phan vuong toi da: 18

Lưu ý: Kết quả 18 không khớp với mảng {2,1,0,4,5,3} (n=6, max partitions ≤ 6). Code gốc có thể có lỗi logic hoặc input khác. Với mảng này: max lần lượt 2,2,2,4,5,5. max==i tại i=2,4,5 → 3 phân vùng.

Độ phức tạp

• Thời gian: O(N) - duyệt một lần.
• Không gian: O(1).

Chứng minh tính đúng đắn

Gọi M(i) = max(arr[0..i]). Phân vùng tại i hợp lệ ⇔ M(i) = i.

• Nếu M(i) = i: Tất cả số 0..i đều xuất hiện trong arr[0..i] (vì là hoán vị). Sắp xếp đoạn này ra 0..i.
• Phần còn lại arr[i+1..N-1] chỉ chứa số > i, độc lập với phần trước.
• Tách tại mọi i thỏa M(i)=i cho số phân vùng tối đa.

Mở rộng: Mảng không phải hoán vị 0..N-1

Nếu mảng chứa số tùy ý, dùng bản đồ vị trí trong mảng đã sắp xếp:

int maxChunksToSorted(vector& arr) {
    vector sorted = arr;
    sort(sorted.begin(), sorted.end());
    unordered_map pos;
    for (int i = 0; i < sorted.size(); i++) pos[sorted[i]] = i;
    
    int count = 0, maxPos = 0;
    for (int i = 0; i < arr.size(); i++) {
        maxPos = max(maxPos, pos[arr[i]]);
        if (maxPos == i) count++;
    }
    return count;
}