Given an array of length n, and an integer k( where k represents the number of elements to remove), we have to pick either the leftmost or the rightmost element of the array and discard it and proceed with the rest of the array. Maximise the sum of the k discarded elements.

Greedy approach wont work here, so I suggested backtracking and then suggested DP via memoization. The interviewer told me that a solution of order O(k) was possible but I couldnt find it. Can someone share how that would work?