# 將數組劃分為 k 個片段，以最大化片段最小值的最大值 > 原文： [https://www.geeksforgeeks.org/divide-array-k-segments-maximize-maximum-segment-minimums/](https://www.geeksforgeeks.org/divide-array-k-segments-maximize-maximum-segment-minimums/) 給定一個由 n 個整數組成的數組，請將其劃分為 k 個分段，并找到 k 個分段的最小值中的最大值。 輸出在分割 k 個子數組的所有方式中可以獲得的最大整數。 **示例**： ``` Input : arr[] = {1, 2, 3, 6, 5} k = 2 Output: 5 Explanation: There are many ways to create two segments. The optimal segments are (1, 2, 3) and (6, 5). Minimum of both segments are 1 and 5, hence the maximum(1, 5) is 5\. Input: -4 -5 -3 -2 -1 k=1 Output: -5 Explanation: only one segment, so minimum is -5. ``` 將有 3 種情況需要考慮。 1. **k > = 3**：當 k 大于 2 時，一個段將僅由{max element}組成，因此最小段的最大值將始終為 max。 2. **k = 2**：對于 k = 2，答案是第一個元素和最后一個元素的最大值。 3. **k = 1**：只有可能的分區是等于整個數組的一個分段。 因此，答案是整個數組上的最小值。 下面是上述方法的實現 ## C++ ```cpp // CPP Program to find maximum value of // maximum of minimums of k segments. #include <bits/stdc++.h> using namespace std; // function to calculate the max of all the // minimum segments int maxOfSegmentMins(int a[], int n, int k) { ????// if we have to divide it into 1 segment ????// then the min will be the answer ????if (k == 1)? ???????return *min_element(a, a+n); ????if (k == 2)? ???????return max(a[0], a[n-1]);?? ????// If k >= 3, return maximum of all ????// elements. ????return *max_element(a, a+n); } // driver program to test the above function int main() { ????int a[] = { -10, -9, -8, 2, 7, -6, -5 }; ????int n = sizeof(a) / sizeof(a[0]); ????int k = 2; ????cout << maxOfSegmentMins(a, n, k); } ``` ## Java ```java // Java Program to find maximum? // value of maximum of minimums // of k segments. import java .io.*; import java .util.*; class GFG { ????// function to calculate? ????// the max of all the? ????// minimum segments ????static int maxOfSegmentMins(int []a, ????????????????????????????????int n,? ????????????????????????????????int k) ????{ ????????// if we have to divide? ????????// it into 1 segment then? ????????// the min will be the answer ????????if (k == 1)? ????????{ ????????????Arrays.sort(a); ????????????????return a[0]; ????????} ????????if (k == 2)? ????????????return Math.max(a[0],? ????????????????????????????a[n - 1]);? ????????// If k >= 3, return? ????????// maximum of all? ????????// elements. ????????return a[n - 1]; ????} ????// Driver Code ????static public void main (String[] args) ????{ ????????int []a = {-10, -9, -8,? ????????????????????2, 7, -6, -5}; ????????int n = a.length; ????????int k = 2; ????????System.out.println( ????????????????maxOfSegmentMins(a, n, k)); ????} } // This code is contributed // by anuj_67\. ``` ## Python3 ```py # Python3 Program to find maximum value of? # maximum of minimums of k segments. # function to calculate the max of all the? # minimum segments? def maxOfSegmentMins(a,n,k): ????# if we have to divide it into 1 segment? ????# then the min will be the answer? ????if k ==1: ????????return min(a) ????if k==2: ????????return max(a[0],a[n-1]) ????# If k >= 3, return maximum of all? ????#? elements.? ????return max(a) # Driver code if __name__=='__main__': ????a = [-10, -9, -8, 2, 7, -6, -5] ????n = len(a) ????k =2 ????print(maxOfSegmentMins(a,n,k)) # This code is contributed by? # Shrikant13 ``` ## C# ```cs // C# Program to find maximum value of // maximum of minimums of k segments. using System; using System.Linq; public class GFG { ????// function to calculate the max ????// of all the minimum segments ????static int maxOfSegmentMins(int []a, ?????????????????????????????int n, int k) ????{ ????????// if we have to divide it into 1 ????????// segment then the min will be ????????// the answer ????????if (k == 1)? ????????????return a.Min(); ????????if (k == 2)? ????????????return Math.Max(a[0], a[n - 1]);? ????????// If k >= 3, return maximum of ????????// all elements. ????????return a.Max(); ????} ????// Driver function ????static public void Main () ????{ ????????int []a = { -10, -9, -8, 2, 7, ?????????????????????????????????-6, -5 }; ????????int n = a.Length; ????????int k = 2; ????????Console.WriteLine( ??????????????????maxOfSegmentMins(a, n, k)); ????} } // This code is contributed by vt_m. ``` ## PHP ```php <?php // PHP Program to find maximum // value of maximum of minimums // of k segments. // function to calculate // the max of all the // minimum segments function maxOfSegmentMins($a, $n, $k) { ????// if we have to divide? ????// it into 1 segment then ????// the min will be the answer ????if ($k == 1)? ????return min($a); ????if ($k == 2)? ????return max($a[0],? ???????????????$a[$n - 1]);? ????// If k >= 3, return? ????// maximum of all elements. ????return max($a); } // Driver Code $a = array(-10, -9, -8,? ????????????2, 7, -6, -5); $n = count($a); $k = 2; echo maxOfSegmentMins($a, $n, $k); // This code is contributed by vits. ?> ``` **輸出**： ``` -5 ``` **時間復雜度**：`O(n)` **輔助空間**：`O(1)` 本文由 [**Raja Vikramaditya**](https://www.facebook.com/raja.vikramaditya.7) 提供。 如果您喜歡 GeeksforGeeks 并希望做出貢獻，則還可以使用 [tribution.geeksforgeeks.org](http://www.contribute.geeksforgeeks.org) 撰寫文章，或將您的文章郵寄至 tribution@geeksforgeeks.org。 查看您的文章出現在 GeeksforGeeks 主頁上，并幫助其他 Geeks。