在C ++中最大化K个连续子数组中的最小值
给定任务是将数组arr[]划分为K个连续的子数组，并在K个连续的子数组的最小值中找到max的最大可能值。
输入项
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
这是一个艰难的情况。在这种情况下，我们将必须制作两个包含最小前缀和后缀的数组，因为该数组只能分为两部分。然后对于数组的每个元素，我们都必须这样做-
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