Shrink the Array

This problem can be solved using dynamic programming.

Our DP will have two parameters—position and number of operation left to be used. So we can have a total of N×K states.

In each state, we will select a segment of the array and call the next state. As we can use maximum K operations, our inner loop will not run more than that.

Thus, our time complexity will be O(N × K2).