Problem statement

https://binarysearch.com/problems/Maximum-Sum-Removing-K-Numbers-From-Ends/

Solution

What we need to find is minimum sum in window of size n - k, than answer is sum of all numbers minus this sum. It can be done for example with use of prefix sums.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, nums, k):
        acc = [0] + list(accumulate(nums))
        w = len(nums) - k
        ans = min(acc[i + w] - acc[i] for i in range(k + 1))
        return sum(nums) - ans