Few days back I got this question in my coding round

You are given N cubes of wood aranged in increasing order.The length of side of ith cube is arr[i] and side lenghts are distinct. The first and last cubes cannot be moved.

We have minimize the maximum diff of cubes arrangement by removing exactly K cubes.

diff=max(arr[i+1]-arr[i]) for 1<i<-N-1

Input:
firs line single Integer N
second line N separated integer arr[i]
third line single Integer K

Example
5
1 2 3 7 8
2

output:
5

by taking ={ 1 3 8 }

I applied bruteforce generating all subset of N-K , only 1 test case passed out of 7
Any optimized solution ?