Minimice la suma de pares que, al eliminar, divide el Array en 3 subarreglos

Dada una array arr de tamaño N , la tarea es encontrar un par de elementos que tengan una suma mínima, que al eliminarse divide la array en 3 subarreglos no vacíos de la array original. Imprime la suma de los elementos de este par.

Entrada: arr[]: {4, 2, 1, 2, 4}
Salida: 4
Explicación:
Los pares de suma mínima son valores (2, 1) y (1, 2) pero seleccionar un par con índices adyacentes no romperá el array en 3 partes. El siguiente par de valores mínimos es (2, 2), que divide la array en {4}, {1}, {4}. Por lo tanto, la respuesta es 2 + 2 = 4.

Entrada: arr[] = {5, 2, 4, 6, 3, 7}
Salida: 5
Explicación:
entre todos los pares que dividen la array en 3 subpartes, el par con valores (2, 3) da la suma mínima.

Enfoque ingenuo: dividir la array en tres subarreglos. Ambos elementos que deben eliminarse deben seguir estas condiciones:

• cualquiera de los puntos finales (índice 0 y N-1 ) no se puede seleccionar.
• los índices adyacentes no se pueden seleccionar.

Entonces, encuentre todas las combinaciones de pares posibles y seleccione la que cumpla con las condiciones anteriores y tenga la suma más baja de todas.

Tiempo Complejidad: O(N ² ) 
Espacio auxiliar: O(N)

Enfoque eficiente : siga los pasos a continuación para resolver este problema de manera eficiente:

1. Cree una array prefixMin, en la que el i-ésimo elemento representa el elemento mínimo desde el 0 hasta el i-ésimo índice en la array arr.
2. Cree una variable ans, para almacenar la respuesta final e inicialícela con INT_MAX.
3. Ahora, ejecute un ciclo para i=3 a i=N-1 (comenzando desde 3 como 0th no se puede seleccionar y este ciclo es para seleccionar el segundo elemento del par, lo que significa que ni siquiera se puede iniciar desde 2 porque entonces las únicas opciones restantes para el primer elemento son 1 y 2, que no siguen las condiciones dadas) y en cada iteración cambia ans al valor mínimo de ans y arr[i]+prefixMin[i-2] .
4. Imprima ans, después de seguir los pasos anteriores.

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 find minimum possible sum
// of pair which breaks the array into 3
// non-empty subarrays
int minSumPair(int arr[], int N)
{
 
    if (N < 5) {
        return -1;
    }
 
    int prefixMin[N];
    prefixMin[0] = arr[0];
 
    // prefixMin[i] contains minimum element till i
    for (int i = 1; i < N - 1; i++) {
        prefixMin[i] = min(arr[i], prefixMin[i - 1]);
    }
 
    int ans = INT_MAX;
 
    for (int i = 3; i < N - 1; i++) {
        ans = min(ans, arr[i] + prefixMin[i - 2]);
    }
 
    return ans;
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 5, 2, 4, 6, 3, 7 };
    int N = sizeof(arr) / sizeof(int);
 
    cout << minSumPair(arr, N) << endl;
 
    return 0;
}

// Java implementation of the above approach
class GFG{
 
// Function to find minimum possible sum
// of pair which breaks the array into 3
// non-empty subarrays
static int minSumPair(int arr[], int N)
{
 
    if (N < 5) {
        return -1;
    }
 
    int []prefixMin = new int[N];
    prefixMin[0] = arr[0];
 
    // prefixMin[i] contains minimum element till i
    for (int i = 1; i < N - 1; i++) {
        prefixMin[i] = Math.min(arr[i], prefixMin[i - 1]);
    }
 
    int ans = Integer.MAX_VALUE;
 
    for (int i = 3; i < N - 1; i++) {
        ans = Math.min(ans, arr[i] + prefixMin[i - 2]);
    }
 
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    // Given array
    int arr[] = { 5, 2, 4, 6, 3, 7 };
    int N = arr.length;
 
    System.out.print(minSumPair(arr, N) +"\n");
 
}
}
 
// This code is contributed by Princi Singh

# Python 3 implementation of the above approach
import sys
 
# Function to find minimum possible sum
# of pair which breaks the array into 3
# non-empty subarrays
def minSumPair(arr, N):
    if(N < 5):
        return -1
 
    prefixMin = [0 for i in range(N)]
    prefixMin[0] = arr[0]
 
    # prefixMin[i] contains minimum element till i
    for i in range(1,N - 1,1):
        prefixMin[i] = min(arr[i], prefixMin[i - 1])
 
    ans = sys.maxsize
 
    for i in range(3,N - 1,1):
        ans = min(ans, arr[i] + prefixMin[i - 2])
 
    return ans
 
# Driver Code
if __name__ == '__main__':
   
    # Given array
    arr = [5, 2, 4, 6, 3, 7]
    N = len(arr)
    print(minSumPair(arr, N))
     
    # This code is contributed by ipg201107.

// C# implementation of the above approach
using System;
 
public class GFG{
 
// Function to find minimum possible sum
// of pair which breaks the array into 3
// non-empty subarrays
static int minSumPair(int []arr, int N)
{
 
    if (N < 5) {
        return -1;
    }
 
    int []prefixMin = new int[N];
    prefixMin[0] = arr[0];
 
    // prefixMin[i] contains minimum element till i
    for (int i = 1; i < N - 1; i++) {
        prefixMin[i] = Math.Min(arr[i], prefixMin[i - 1]);
    }
 
    int ans = int.MaxValue;
 
    for (int i = 3; i < N - 1; i++) {
        ans = Math.Min(ans, arr[i] + prefixMin[i - 2]);
    }
 
    return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
   
    // Given array
    int []arr = { 5, 2, 4, 6, 3, 7 };
    int N = arr.Length;
 
    Console.Write(minSumPair(arr, N) +"\n");
 
}
}
 
// This code is contributed by shikhasingrajput

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Function to find minimum possible sum
        // of pair which breaks the array into 3
        // non-empty subarrays
        function minSumPair(arr, N) {
 
            if (N < 5) {
                return -1;
            }
 
            let prefixMin = new Array(N).fill(0);
            prefixMin[0] = arr[0];
 
            // prefixMin[i] contains minimum element till i
            for (let i = 1; i < N - 1; i++) {
                prefixMin[i] = Math.min(arr[i], prefixMin[i - 1]);
            }
 
            let ans = Number.MAX_VALUE;
 
            for (let i = 3; i < N - 1; i++) {
                ans = Math.min(ans, arr[i] + prefixMin[i - 2]);
            }
 
            return ans;
        }
 
        // Driver Code
 
        // Given array
        let arr = [5, 2, 4, 6, 3, 7];
        let N = arr.length;
 
        document.write(minSumPair(arr, N));
 
     // This code is contributed by Potta Lokesh
 
    </script>

5

Complejidad de tiempo : O(n)

Complejidad espacial : O(n)