Điểm phân hoạch là phần tử mà **tất cả phần tử bên trái nhỏ hơn nó** và **tất cả phần tử bên phải lớn hơn nó**. Tìm giá trị phần tử đó. Ví dụ: {4,3,5,6,7} → 5 (bên trái: 4,3 < 5; bên phải: 6,7 > 5).
Phương pháp: Vét cạn O(n²)
- Với mỗi i từ 0 đến n-1:
- Kiểm tra tất cả j < i: arr[j] < arr[i].
- Kiểm tra tất cả j > i: arr[j] > arr[i].
- Nếu thỏa mãn → trả về arr[i].
Ví dụ mã nguồn
#include <bits/stdc++.h>
using namespace std;
int findPartition(int arr[], int n) {
for (int i=0;i= arr[i]) { ok=false; break; }
if (!ok) continue;
for (int j=i+1;j
Kết quả
5
Có thể tối ưu O(n) bằng mảng prefix max và suffix min.