배열 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
아래 프로그램에서 사용하는 접근 방식은 다음과 같습니다.
-
작업을 보면 K=1, k=2, k>=3의 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