¿Encuentre la suma máxima de elementos eliminados de la cabeza o la cola?

Se le da una pila de N enteros de manera que el primer elemento representa la parte superior de la pila y el último elemento representa la parte inferior de la pila. Debe extraer al menos un elemento de la pila. En cualquier momento, puede convertir la pila en una cola. La parte inferior de la pila representa el frente de la cola. No puede volver a convertir la cola en una pila. Su tarea es eliminar exactamente K elementos de modo que se maximice la suma de los K elementos eliminados. Imprime la máxima suma posible M de los K elementos eliminados

Entrada: N=10, K=4
pila = [10 9 1 2 3 4 5 6 7 8]

Salida: 34

Explicación:
saca dos elementos de la pila. es decir, {10,9}
Luego, convierta la pila en cola y elimine los primeros 2 elementos de la cola. es decir, {8,7}.
La suma máxima posible es 10+9+8+7 = 34

Estaba pensando en resolverlo con algo codicioso, con un código como el siguiente:

stk = [10, 9, 1, 30, 3, 4, 5, 100, 1, 8]
n = 10
k = 4
removed = 0
top = 0
sum = 0
bottom = len(stk)-1
while removed < k:
 if stk[top] >= stk[bottom]:
 sum += stk[top]
 top += 1
 
 else:
 sum += stk[bottom]
 bottom -= 1
 removed += 1
print(sum)

en un caso de prueba normal (dado uno) funcionará, pero fallará en muchos otros escenarios como:

[10, 9, 1, 30, 3, 4, 5, 100, 1, 8]

¿Alguna sugerencia sobre cómo mejorar esto?

Solución del problema

La estructura de datos le da la opción de seleccionar 1,...,n valores desde la parte superior de la estructura y luego m elementos desde la parte inferior de la estructura donde K = m+n. Puede encontrar el máximo si comienza sumando los primeros elementos K de la estructura y luego avanza hacia atrás reemplazando el elemento n con el primer elemento desde atrás. Trabajando hacia atrás para llegar a un solo elemento de pila. Mantenga un registro del máximo a lo largo del camino.

En pitón:

lst = [10, 9, 1, 30, 3, 4, 5, 100, 1, 8]
K = 4
sum_ = sum(lst[0:K])
max_so_far = sum_
for i in range(K-1):
 sum_ = sum_ - lst[K-1-i] + lst[-i-1]
 max_so_far = max(sum_, max_so_far)
print(max_so_far)

El tiempo de ejecución es O(n).