ภารกิจคือการแบ่งอาร์เรย์ arr[] เป็นอาร์เรย์ย่อย K ที่ต่อเนื่องกัน และค้นหาค่าสูงสุดที่เป็นไปได้จากค่าต่ำสุดของอาร์เรย์ย่อย K ที่ต่อเนื่องกัน
ป้อนข้อมูล
arr[]={2,8,4,3,9,1,5}, K=3 ผลผลิต
9
คำอธิบาย − อาร์เรย์ย่อยที่ต่อเนื่องกัน 3 ชุดที่สามารถสร้างได้คือ:{2, 8, 4, 3}, {9} และ {1, 5}
ค่าต่ำสุดของอาร์เรย์เหล่านี้คือ:(2, 9, 1)
ค่าสูงสุดของทั้งสามนี้คือ 9.
ป้อนข้อมูล
arr[] = { 8, 4, 1, 9, 11}, K=1 ผลผลิต
11
แนวทางที่ใช้ในโปรแกรมด้านล่างดังนี้
-
หากดูจากงานแล้ว สามารถแบ่งได้เป็น 3 กรณี คือ เมื่อ K=1, k=2 และ k>=3
-
กรณีที่ 1 − K=1
เมื่อ k=1 อาร์เรย์ย่อยเท่ากับอาร์เรย์ ดังนั้นค่าต่ำสุดในอาร์เรย์จะเป็นเอาต์พุต
-
กรณีที่ 2 − K=2
นี่เป็นกรณีที่ยาก ในกรณีนี้ เราจะต้องสร้างอาร์เรย์ 2 ชุด โดยจะมีส่วนนำหน้าและส่วนต่อท้ายขั้นต่ำ เนื่องจากอาร์เรย์จะแบ่งออกเป็น 2 ส่วนเท่านั้น จากนั้นสำหรับทุกองค์ประกอบของอาร์เรย์ เราจะต้องทำเช่นนั้น −
MaxValue =max(MaxValue, max(ค่าต่ำสุดนำหน้าที่ i, ค่าต่อท้ายค่าสูงสุดที่ i+1))
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
/* Function to find the maximum possible value
of the maximum of minimum of K sub-arrays*/
int Max(const int* arr, int size, int K){
dint Max;
int Min;
//Obtain maximum and minimum
for (int i = 0; i < size; i++){
Min = min(Min, arr[i]);
Max = max(Max, arr[i]);
}
//When K=1, return minimum value
if (K == 1){
return Min;
}
//When K>=3, return maximum value
else if (K >= 3){
return Max;
}
/*When K=2 then make prefix and suffix minimums*/
else{
// Arrays to store prefix and suffix minimums
int Left[size], Right[size];
Left[0] = arr[0];
Right[size - 1] = arr[size - 1];
// Prefix minimum
for (int i = 1; i < size; i++){
Left[i] = min(Left[i - 1], arr[i]);
}
// Suffix minimum
for (int i = size - 2; i >= 0; i--){
Right[i] = min(Right[i + 1], arr[i]);
}
int MaxValue=INT_MIN;
// Get the maximum possible value
for (int i = 0; i < size - 1; i++){
MaxValue = max(MaxValue, max(Left[i], Right[i + 1]));
}
return MaxValue;
}
}
int main(){
int arr[] = {9,4,12,5,6,11};
int size = sizeof(arr) / sizeof(arr[0]);
int K = 2;
cout<<"Maximize the maximum among minimum of K consecutive sub-arrays is: "<<Max(arr, size, K);
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น เราจะได้ผลลัพธ์ดังต่อไปนี้ -
Maximize the maximum among minimum of K consecutive sub-arrays is: 11
