Tối đa hóa giá trị lớn nhất trong số tối thiểu của K mảng con liên tiếp trong C ++

Được giao nhiệm vụ là chia một mảng arr [] thành K mảng con liên tiếp và tìm giá trị lớn nhất có thể có của giá trị lớn nhất trong số giá trị nhỏ nhất của K dãy con liên tiếp.

Đầu vào

arr[]={2,8,4,3,9,1,5}, K=3

Đầu ra

9

Giải thích - 3 mảng con liên tiếp có thể được tạo là:{2, 8, 4, 3}, {9} và {1, 5}

Giá trị tối thiểu của tất cả các mảng này là:(2, 9, 1)

Giá trị lớn nhất trong số ba giá trị này là 9.

Đầu vào

arr[] = { 8, 4, 1, 9, 11}, K=1

Đầu ra

11

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

• Nếu chúng ta nhìn vào nhiệm vụ, nó có thể được chia thành 3 trường hợp - khi K =1, k =2 và k> =3.

• Trường hợp 1 - K =1

  Khi k =1, mảng con bằng với chính mảng và do đó giá trị nhỏ nhất trong mảng sẽ là giá trị đầu ra.

• Trường hợp 2 - K =2

  Đây là một trường hợp khó khăn. Trong trường hợp này, chúng ta sẽ phải tạo hai mảng chứa tối thiểu tiền tố và hậu tố vì mảng chỉ có thể được chia thành 2 phần. Sau đó, đối với mọi phần tử của mảng, chúng ta sẽ phải làm như vậy -

  MaxValue =max (MaxValue, max (giá trị nhỏ nhất của tiền tố ở i, giá trị lớn nhất của hậu tố ở i + 1))

Ví dụ

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, chúng ta sẽ nhận được kết quả sau -

Maximize the maximum among minimum of K consecutive sub-arrays is: 11