สมมติว่าเราให้อาร์เรย์ arr ซึ่งเป็นการเรียงสับเปลี่ยนของ [0, 1, ..., arr.length - 1] เราต้องแยกอาร์เรย์ออกเป็น "ส่วนย่อย" จำนวนหนึ่ง " หรือพาร์ติชั่น และแยกแต่ละพาร์ติชั่น ดังนั้นหลังจากเชื่อมเข้าด้วยกันแล้ว ผลลัพธ์จะเป็นอาร์เรย์ที่จัดเรียง ดังนั้นหากอาร์เรย์เป็นเหมือน [1,0,2,3,4] ผลลัพธ์จะเป็น 4 เนื่องจากเราสามารถแบ่งออกเป็นสองพาร์ติชั่นเช่น [1, 0] และ [2,3,4] แต่สิ่งนี้สามารถทำได้ ให้เป็นจริงด้วยว่า [1, 0], [2], [3], [4] นี่คือจำนวนชิ้นส่วนสูงสุดที่เป็นไปได้ ดังนั้นเอาต์พุตจึงเป็น 4
จำนวนชิ้นส่วนที่เราสามารถทำได้มากที่สุดคือเท่าใด
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ans :=0, minVal :=inf, n :=ขนาดของ arr และ maxVal :=-inf
- สำหรับฉันอยู่ในช่วง 0 ถึง n
- maxVal :=สูงสุดของ arr[i] และ maxVal
- ถ้า maxVal =i ให้เพิ่ม ans ขึ้น 1
- คืนสินค้า
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxChunksToSorted(vector<int>& arr) {
int ans = 0;
int minVal = INT_MAX;
int n = arr.size();
int maxVal = INT_MIN;
for(int i = 0; i < n; i++){
maxVal = max(arr[i], maxVal);
if(maxVal == i){
ans++;
}
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {1,0,2,3,4};
cout << (ob.maxChunksToSorted(v));
} อินพุต
[1,0,2,3,4]
ผลลัพธ์
4
