Remove K consecutive elements from array, so that amplitude of remaining elements is minimal.

RemoveKMinAmplitude.py

# Reference : https://stackoverflow.com/questions/69236733/remove-n-consecutive-elements-from-array-so-that-amplitude-of-remaining-element/69237657#69237657
# remove K consecutive elements from array, so that amplitude of remaining elements is minimal

from itertools import accumulate as acc
from math import inf

A = [3,5,1,3,9,8]
B = A[::-1]
K = 3
N = len(A)

# Get prefix max and min of all elements
pre = list(zip(acc(A, min, initial=inf), acc(A, max, initial=-inf)))

# Get suffix max and min of all elements
suf = list(zip(list(acc(B, min, initial=inf))[::-1], list(acc(B, max, initial=-inf))[::-1]))

# Zip only those which are in window of N-K for prefix and in window of N-K+1 for suffix
Z = list(zip(pre[:N-K], suf[N-K+1:]))

# Calc minimum difference between the elements left after droping K consecutive elements
s = inf
for left,right in Z:
    a = max(left[1],right[1])
    b = min(left[0], right[0])
    s = min(s, a-b)
print(s)