Dada una array arr[] que tiene un tamaño de 3*N , la tarea es eliminar N elementos y dividir toda la array en dos partes iguales de modo que la diferencia de la suma de la subarreglo izquierda y la subarreción derecha rinda al máximo.
Ejemplos:
Entrada: arr[] = [5, 4, 4, 2, 3, 3]
Salida: 4
Explicación: Los elementos ‘2’ que se eliminarán son [4, 3].
y cuando divide la array en dos partes iguales después de la eliminación
subarreglo izquierdo = [5, 4], subarreglo derecho = [2, 3].
La suma de la diferencia entre ellos es (9-5) = 4Entrada: arr[] = [4, 5, 6, 1, 2, 8, 7, 9, 3]
Salida: 9
Acercarse:
Divida la array en dos subarreglos en algún punto i ( N <= i <= 2 * N ). Eliminamos i – N elementos más pequeños del primer subarreglo y (2 * N – i) elementos más grandes del segundo subarreglo. De esa manera, para una división dada, obtenemos la suma_primero más grande posible y la suma_segundo más pequeña posible.
Usar el montón Max y Min para realizar un seguimiento de los elementos más pequeños y más grandes, respectivamente. Y actualiza la diferencia.
Siga los pasos a continuación para implementar la idea:
- Inicialice una variable final_diff para almacenar la diferencia máxima entre el subarreglo izquierdo y derecho después de eliminar N elementos.
- Ejecute un ciclo for de N a 2*N y arr[] en dos mitades izquierda y derecha.
- Elimine i – N elementos más pequeños de la array izquierda y 2*N – i elementos más grandes de la array derecha utilizando Min y Max heap .
- Calcule la suma de N valores más grandes en la array izquierda y N valores más pequeños en la array derecha y descubra la diferencia entre ellos y guárdela en la variable Curr_diff .
- Maximiza el valor de final_diff con curr_diff .
- Devuelve el valor de final_diff.
A continuación se muestra la implementación.
Python3
import copy
import heapq
from collections import Counter
# This function return the (1, n-1) min and max
# elements which are t be discarded from the array
def best_remove(left, right):
temp = []
heapq.heapify(left)
heapq.heapify(right)
if len(left) == n and len(right) > n:
# remove all n elements from the right side
temp.extend(heapq.nlargest(n, right))
elif len(right) == n and len(left) > n:
# remove all element from the left side
temp.extend(heapq.nsmallest(n, left))
else:
x = len(left) - n
temp.extend(heapq.nsmallest(x, left)+heapq.nlargest(n-x, right))
return temp
def remove_elements(parent, child):
f_s = Counter(child)
# storing all the elements of right
# part to preserve the order incase of duplicates
r_h = []
for i in parent:
if i in f_s and f_s[i] > 0:
f_s[i] -= 1
else:
r_h.append(i)
# print("after r", left + r_h)
return r_h
# Remove the child from parent
# divide the array
# sum the left and right elemets
# track the curr max sum until the for loops terminates
# return the final max diffrence
# print(parent, n, child, m)
# print(left, right)
def max_diff(arr): # function that calculats the sum of maximum diffrence between two arrays
# print(arr)
mid = len(arr)//2
left = sum(arr[:mid])
right = sum(arr[mid:])
return left-right
arr = [7, 9, 5, 8, 1, 3]
n = len(arr)//3
final_max = -float("inf")
# starting from the index 2
for i in range(n, 2 * n + 1):
left = arr[:i] # dividing the left
right = arr[i:] # dividing te right sub array
# print(left, right)
# functions which returns the best elements to be removed from both sub arrays
best_remove_elements = best_remove(left, right)
# print(best_remove_elements)
dup = []
# copying the original array so that the changes might not reflct
dup = copy.deepcopy(arr)
# function that returns the array after removing the best_remove elements
remove_element = remove_elements(dup, best_remove_elements)
# print(remove_element)
# return(remove_element)
curr_max = max_diff(remove_element) # tracking the maximum
final_max = max(final_max, curr_max)
print("The maximum diffrence between S1 and S2 is", final_max)
The maximum diffrence between S1 and S2 is 13
Complejidad de tiempo: (N*log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por saikumarkudikala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA