Diferencia mínima entre el valor más alto y el más pequeño de las minas distribuidas

Dadas n empresas y m minas de aceite con valores, la tarea es distribuir las minas entre n empresas de manera justa. Esa es la diferencia entre la empresa que obtiene la mayor suma de valores de las minas y la que obtiene el menor debe ser mínima. Calcule la diferencia mínima. Tenga en cuenta que las minas de petróleo distribuidas a cada empresa deben estar adyacentes entre sí. También,

Ejemplos:

Entrada: n = 2, m = 4
valores de minas = [6, 10, 13, 2]
Salida: 1 –> minas distribuidas como {(6, 10), (13, 2)}, por lo que la salida es (6+ 10) – (13+2) = 1

Entrada: n = 3, m = 4
valores de minas = [6, 10, 13, 2]
Salida: 9 –> minas distribuidas como {(6), (10), (13, 2)}, por lo que la salida es ( 13+2) – (6) = 9

Fuente: pregunta de la ronda de codificación de Samsung RnD 3 horas

Acercarse:

1. Construya una array tal que el valor en cada índice contenga la suma de todos los valores actuales y anteriores en la array.
2. Incluya el último valor en la array en nuestra array de solución.
3. Construya de forma recursiva todas las arrays de soluciones posibles seleccionando valores n-1 de los valores m-1 dados a partir del penúltimo índice (ya que el último valor de la array ya se ha incluido en nuestra array de soluciones).
4. Reste el valor en el siguiente índice del valor en el índice actual en la array de solución para los valores en cada índice excepto el último valor. Calcule la diferencia entre el valor más alto y el más bajo para todas las arrays de soluciones y devuelva el mínimo.

Tomemos un ejemplo para comprender el enfoque anterior paso a paso:

Inicialmente, la entrada se proporciona de la siguiente manera:

Después del paso 1 , nuestra array se parece a la array que se muestra a continuación:

Después del paso 2 , la array de solución se parece a la array que se muestra a continuación:

Después del paso 3 , obtenemos las siguientes arrays de soluciones posibles:

Después del paso 4 , nuestras arrays de solución se ven como las arrays que se muestran a continuación. Luego calculamos la diferencia entre el valor máximo y mínimo en la array para todas las arrays y devolvemos el que es mínimo (en este caso, 9).

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

# Python3 code to minimize the difference 
# between the highest and lowest value containing company
  
# This function constructs the solution array 
# recursively and returns the difference 
# between the highest and lowest value.
def func(solArr, arr, index, n):
      
    # If the values have been distributed,
    # compute the difference
    if n == 0:
        for i in range(len(solArr)-1):
            solArr[i] = solArr[i] - solArr[i + 1]
              
        return max(solArr) - min(solArr)
          
    else:
          
        # solArr can be constructed even if we 
        # don't include the current value
        if index >= n:
            return min(func(solArr[:] + [arr[index]], arr, index-1, n-1), 
                       func(solArr[:], arr, index-1, n))
          
        # solArr can't be constructed hence 
        # we have to include the current value    
        else:
            return func(solArr[:] + [arr[index]], arr, index-1, n-1)
              
n = 3
arr = [6, 10, 13, 2]
  
# Construct array such that value at each index 
# contains the sum of current and all previous 
# values in the array.
for i in range(1, len(arr)):
    arr[i] += arr[i-1]
  
# Include the last value of 
# the array in our solution array.
solArr = [arr[-1]]
      
print(func(solArr[:], arr, len(arr)-2, n-1))

9

Complejidad de tiempo:
Complejidad de espacio: