Maximizar el máximo entre el mínimo de K subarreglos consecutivos

Dado un entero K y una array arr[] , la tarea es dividir la array arr[] en K subarreglos consecutivos para encontrar el valor máximo posible del máximo entre el valor mínimo de K subarreglos consecutivos .

Ejemplos: 

Entrada: arr[] = {1, 2, 3, 4, 5}, K = 2 
Salida: 5 
Divida la array como [1, 2, 3, 4] y [5]. El mínimo de los 2 subconjuntos consecutivos es 1 y 5. 
Máximo (1, 5) = 5. Esta división garantiza el valor máximo posible.

Entrada: arr[] = {-4, -5, -3, -2, -1}, K = 1 
Salida: -5 
Solo es posible una subarray. Por lo tanto, min(-4, -5, -3, -2, -1) = -5 
 

Planteamiento: La solución se puede dividir en 3 casos posibles:  

1. Cuando K = 1: En este caso, la respuesta siempre es igual al mínimo de la array, ya que la array se divide en una sola sub-array, es decir, la propia array.
2. Cuando K ≥ 3: En este caso, la respuesta siempre es igual al máximo del arreglo. Cuando la array deba dividirse en 3 o más segmentos, mantenga siempre un segmento que contenga solo un elemento de la array, es decir, el elemento máximo.
3. Cuando K = 2: Este es el caso más complicado. Solo habrá un prefijo y un sufijo, ya que solo puede haber dos subarreglos. Mantenga una serie de mínimos de prefijos y mínimos de sufijos. Luego, para cada elemento arr[i] , actualice ans = max(ans, max(prefijo valor mínimo en i, sufijo valor mínimo en i + 1)) .

A continuación se muestra la implementación del enfoque anterior:  

// C++ implementation of the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return maximum possible value
// of maximum of minimum of K sub-arrays
int maximizeMinimumOfKSubarrays(const int* arr, int n, int k)
{
    int m = INT_MAX;
    int M = INT_MIN;
 
    // Compute maximum and minimum
    // of the array
    for (int i = 0; i < n; i++) {
        m = min(m, arr[i]);
        M = max(M, arr[i]);
    }
 
    // If k = 1 then return the
    // minimum of the array
    if (k == 1) {
        return m;
    }
    // If k >= 3 then return the
    // maximum of the array
    else if (k >= 3) {
        return M;
    }
 
    // If k = 2 then maintain prefix
    // and suffix minimums
    else {
 
        // Arrays to store prefix
        // and suffix minimums
        int L[n], R[n];
 
        L[0] = arr[0];
        R[n - 1] = arr[n - 1];
 
        // Prefix minimum
        for (int i = 1; i < n; i++)
            L[i] = min(L[i - 1], arr[i]);
 
        // Suffix minimum
        for (int i = n - 2; i >= 0; i--)
            R[i] = min(R[i + 1], arr[i]);
 
        int maxVal = INT_MIN;
 
        // Get the maximum possible value
        for (int i = 0; i < n - 1; i++)
            maxVal = max(maxVal, max(L[i], R[i + 1]));
 
        return maxVal;
    }
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
 
    cout << maximizeMinimumOfKSubarrays(arr, n, k);
 
    return 0;
}

// Java implementation of the above approach
class GFG {
 
    // Function to return maximum possible value
    // of maximum of minimum of K sub-arrays
    static int maximizeMinimumOfKSubarrays(int arr[], int n, int k)
    {
        int m = Integer.MAX_VALUE;
        int M = Integer.MIN_VALUE;
 
        // Compute maximum and minimum
        // of the array
        for (int i = 0; i < n; i++) {
            m = Math.min(m, arr[i]);
            M = Math.max(M, arr[i]);
        }
 
        // If k = 1 then return the
        // minimum of the array
        if (k == 1) {
            return m;
        }
 
        // If k >= 3 then return the
        // maximum of the array
        else if (k >= 3) {
            return M;
        }
 
        // If k = 2 then maintain prefix
        // and suffix minimums
        else {
 
            // Arrays to store prefix
            // and suffix minimums
            int L[] = new int[n], R[] = new int[n];
 
            L[0] = arr[0];
            R[n - 1] = arr[n - 1];
 
            // Prefix minimum
            for (int i = 1; i < n; i++)
                L[i] = Math.min(L[i - 1], arr[i]);
 
            // Suffix minimum
            for (int i = n - 2; i >= 0; i--)
                R[i] = Math.min(R[i + 1], arr[i]);
 
            int maxVal = Integer.MIN_VALUE;
 
            // Get the maximum possible value
            for (int i = 0; i < n - 1; i++)
                maxVal = Math.max(maxVal, Math.max(L[i], R[i + 1]));
 
            return maxVal;
        }
    }
 
    // Driver code
    public static void main(String args[])
    {
        int arr[] = { 1, 2, 3, 4, 5 };
        int n = arr.length;
        int k = 2;
 
        System.out.println(maximizeMinimumOfKSubarrays(arr, n, k));
    }
}
 
// This code is contributed by Arnab Kundu

# Python3 implementation of the above approach
import sys
 
# Function to return maximum possible value
# of maximum of minimum of K sub-arrays
def maximizeMinimumOfKSubarrays(arr, n, k) :
     
    m = sys.maxsize;
    M = -(sys.maxsize - 1);
 
    # Compute maximum and minimum
    # of the array
    for i in range(n) :
        m = min(m, arr[i]);
        M = max(M, arr[i]);
 
    # If k = 1 then return the
    # minimum of the array
    if (k == 1) :
        return m;
         
    # If k >= 3 then return the
    # maximum of the array
    elif (k >= 3) :
        return M;
 
    # If k = 2 then maintain prefix
    # and suffix minimums
    else :
         
        # Arrays to store prefix
        # and suffix minimums
        L = [0] * n;
        R = [0] * n;
         
        L[0] = arr[0];
        R[n - 1] = arr[n - 1];
         
        # Prefix minimum
        for i in range(1, n) :
            L[i] = min(L[i - 1], arr[i]);
         
        # Suffix minimum
        for i in range(n - 2, -1, -1) :
            R[i] = min(R[i + 1], arr[i]);
         
        maxVal = -(sys.maxsize - 1);
         
        # Get the maximum possible value
        for i in range(n - 1) :
            maxVal = max(maxVal, max(L[i],
                                 R[i + 1]));
         
        return maxVal;
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 1, 2, 3, 4, 5 ];
    n = len(arr);
    k = 2;
 
    print(maximizeMinimumOfKSubarrays(arr, n, k));
     
# This code is contributed by Ryuga

// C# implementation of above approach
using System;
 
public class GFG {
 
    // Function to return maximum possible value
    // of maximum of minimum of K sub-arrays
    static int maximizeMinimumOfKSubarrays(int[] arr, int n, int k)
    {
        int m = int.MaxValue;
        int M = int.MinValue;
 
        // Compute maximum and minimum
        // of the array
        for (int i = 0; i < n; i++) {
            m = Math.Min(m, arr[i]);
            M = Math.Max(M, arr[i]);
        }
 
        // If k = 1 then return the
        // minimum of the array
        if (k == 1) {
            return m;
        }
 
        // If k >= 3 then return the
        // maximum of the array
        else if (k >= 3) {
            return M;
        }
 
        // If k = 2 then maintain prefix
        // and suffix minimums
        else {
 
            // Arrays to store prefix
            // and suffix minimums
            int[] L = new int[n];
            int[] R = new int[n];
 
            L[0] = arr[0];
            R[n - 1] = arr[n - 1];
 
            // Prefix minimum
            for (int i = 1; i < n; i++)
                L[i] = Math.Min(L[i - 1], arr[i]);
 
            // Suffix minimum
            for (int i = n - 2; i >= 0; i--)
                R[i] = Math.Min(R[i + 1], arr[i]);
 
            int maxVal = int.MinValue;
 
            // Get the maximum possible value
            for (int i = 0; i < n - 1; i++)
                maxVal = Math.Max(maxVal, Math.Max(L[i], R[i + 1]));
 
            return maxVal;
        }
    }
 
    // Driver code
    public static void Main()
    {
        int[] arr = { 1, 2, 3, 4, 5 };
        int n = arr.Length;
        int k = 2;
 
        Console.WriteLine(maximizeMinimumOfKSubarrays(arr, n, k));
    }
}
/* This code contributed by PrinciRaj1992 */

<?php
// PHP implementation of the above approach
 
// Function to return maximum possible value
// of maximum of minimum of K sub-arrays
function maximizeMinimumOfKSubarrays($arr, $n, $k)
{
    $m = PHP_INT_MAX;
    $M = PHP_INT_MIN;
 
    // Compute maximum and minimum
    // of the array
    for ($i = 0; $i < $n; $i++)
    {
        $m = min($m, $arr[$i]);
        $M = max($M, $arr[$i]);
    }
 
    // If k = 1 then return the
    // minimum of the array
    if ($k == 1)
    {
        return $m;
    }
     
    // If k >= 3 then return the
    // maximum of the array
    else if ($k >= 3)
    {
        return $M;
    }
 
    // If k = 2 then maintain prefix
    // and suffix minimums
    else
    {
 
        // Arrays to store prefix
        // and suffix minimums
        $L[0] = $arr[0];
        $R[$n - 1] = $arr[$n - 1];
 
        // Prefix minimum
        for ($i = 1; $i < $n; $i++)
            $L[$i] = min($L[$i - 1], $arr[$i]);
 
        // Suffix minimum
        for ($i = $n - 2; $i >= 0; $i--)
            $R[$i] = min($R[$i + 1], $arr[$i]);
 
        $maxVal = PHP_INT_MIN;
 
        // Get the maximum possible value
        for ($i = 0; $i < $n - 1; $i++)
            $maxVal = max($maxVal,
                      max($L[$i], $R[$i + 1]));
 
        return $maxVal;
    }
}
 
// Driver code
$arr = array( 1, 2, 3, 4, 5 );
$n = sizeof($arr);
$k = 2;
 
echo maximizeMinimumOfKSubarrays($arr, $n, $k);
 
// This code is contributed
// by Akanksha Rai
?>

<script>
 
    // JavaScript implementation of above approach
     
    // Function to return maximum possible value
    // of maximum of minimum of K sub-arrays
    function maximizeMinimumOfKSubarrays(arr, n, k)
    {
        let m = Number.MAX_VALUE;
        let M = Number.MIN_VALUE;
   
        // Compute maximum and minimum
        // of the array
        for (let i = 0; i < n; i++) {
            m = Math.min(m, arr[i]);
            M = Math.max(M, arr[i]);
        }
   
        // If k = 1 then return the
        // minimum of the array
        if (k == 1) {
            return m;
        }
   
        // If k >= 3 then return the
        // maximum of the array
        else if (k >= 3) {
            return M;
        }
   
        // If k = 2 then maintain prefix
        // and suffix minimums
        else {
   
            // Arrays to store prefix
            // and suffix minimums
            let L = new Array(n);
            L.fill(0);
            let R = new Array(n);
            R.fill(0);
   
            L[0] = arr[0];
            R[n - 1] = arr[n - 1];
   
            // Prefix minimum
            for (let i = 1; i < n; i++)
                L[i] = Math.min(L[i - 1], arr[i]);
   
            // Suffix minimum
            for (let i = n - 2; i >= 0; i--)
                R[i] = Math.min(R[i + 1], arr[i]);
   
            let maxVal = Number.MIN_VALUE;
   
            // Get the maximum possible value
            for (let i = 0; i < n - 1; i++)
                maxVal = Math.max(maxVal, Math.max(L[i], R[i + 1]));
   
            return maxVal;
        }
    }
     
    let arr = [ 1, 2, 3, 4, 5 ];
    let n = arr.length;
    let k = 2;
 
    document.write(maximizeMinimumOfKSubarrays(arr, n, k));
     
</script>

5

Complejidad temporal : O(N) 
Espacio auxiliar: O(N)