C++のK個の連続するサブアレイの最小値の中で最大値を最大化する

これらすべての配列の最小値は次のとおりです：（2、9、1）

これら3つのうち最大値は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