資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中求K個連續子陣列的最小值中的最大值
任務是將陣列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
這是一個棘手的情況。在這種情況下，我們將不得不建立兩個陣列，它們將包含字首最小值和字尾最小值，因為陣列只能分成兩部分。然後，對於陣列的每個元素，我們將執行以下操作：
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
更新於：2020年8月14日
204 次瀏覽
廣告