เราได้รับอาร์เรย์ของตัวเลข N โดยมีองค์ประกอบอยู่ในช่วง 0 และ N-1 องค์ประกอบไม่เรียงลำดับ เป้าหมายคือการหาจำนวนพาร์ติชั่นสูงสุดของอาร์เรย์ที่สามารถจัดเรียงทีละรายการ จากนั้นจึงนำมาต่อกันเพื่อสร้างอาร์เรย์ที่เรียงความยาวทั้งหมด N
แต่ละพาร์ติชั่นถูกเลือกเพื่อให้องค์ประกอบในนั้นไม่ถูกจัดเรียง สำหรับตัวเลข N ที่อยู่ระหว่าง 0 ถึง N-1 องค์ประกอบที่จัดเรียงจะอยู่ที่ดัชนีเท่ากับค่า 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]
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
เราใช้อาร์เรย์จำนวนเต็ม Num[] ที่เริ่มต้นด้วยตัวเลขในช่วง 0 ถึง N
-
ฟังก์ชันพาร์ติชั่น(int arr[], int n ) รับอาร์เรย์และความยาวเป็นพารามิเตอร์และส่งคืนจำนวนพาร์ติชั่นสูงสุดที่สามารถจัดเรียงแยกกันเพื่อจัดเรียงทั้งอาร์เรย์
-
จำนวนพาร์ติชั่นเริ่มต้นคือ 0 ค่าสูงสุดเริ่มต้นอยู่ใน maxx เป็น arr[0].
-
สำหรับองค์ประกอบทั้งหมดเริ่มต้นจากองค์ประกอบด้านซ้ายสุด ค้นหาว่ามากกว่า maxx หรือไม่
-
ถ้า arr[i]>maxx เป็นจริง อัปเดต maxx.
-
หาก maxx และดัชนีปัจจุบันเท่ากัน ( maxx==i ) ดังนั้นองค์ประกอบทั้งหมดไม่เกิน i เป็นส่วนหนึ่งของพาร์ติชันเดียว จำนวนที่เพิ่มขึ้น
-
ทำสิ่งนี้กับองค์ประกอบที่เหลือทางด้านขวาจนจบ
-
ส่งคืนผลลัพธ์เป็นการนับ
ตัวอย่าง
#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
