Find the max sum of removed elements from head or tail?-CodePudding

You are given a stack of N integers such that the first element represents the top of the stack and the last element represents the bottom of the stack. You need to pop at least one element from the stack. At any one moment, you can convert stack into a queue. The bottom of the stack represents the front of the queue. You cannot convert the queue back into a stack. Your task is to remove exactly K elements such that the sum of the K removed elements is maximised. Print the maximum possible sum M of the K removed elements

Input: N=10, K=4
stack = [10 9 1 2 3 4 5 6 7 8]

Output: 34

Explanation:
Pop two elements from the stack. i.e {10,9}
Then convert the stack into queue and remove first 2 elements from the queue. i.e {8,7}.
The maximum possible sum is 10 9 8 7 = 34

I was thinking of solving it with greedy algo, with code like following:

stk = [10, 9, 1, 30, 3, 4, 5, 100, 1, 8]
n = 10
k = 4

removed = 0
top = 0
sum = 0
bottom = len(stk)-1

while removed < k:
    if stk[top] >= stk[bottom]:
        sum  = stk[top]
        top  = 1
        
    else:
        sum  = stk[bottom]
        bottom -= 1
    removed  = 1

print(sum)

under normal test case(given one) it'll work, but it'll fail in many other scenarios like:

[10, 9, 1, 30, 3, 4, 5, 100, 1, 8]

Any suggestions on how to improve on this?

CodePudding user response：

The data structure gives you the option to select 1,...,n values from the stop of the structure and then m elements from the bottom of the structure where K = m n. You can find the maximum by starting out with summing the first K elements of the structure and then work your way backwards by replacing the n'th element with the first element from the back. Working backwards to you get to only one stack element. Keep track of the maximum along the way.

In python:

lst = [10, 9, 1, 30, 3, 4, 5, 100, 1, 8]

K = 4

sum_ = sum(lst[0:K])
max_so_far = sum_
for i in range(K-1):
    sum_ = sum_ - lst[K-1-i]   lst[-i-1]
    max_so_far = max(sum_, max_so_far)
print(max_so_far)

The running time is O(n).

CodePudding user response：

If you carefully look at the problem, it basically boils down to:

Select x elements from the start and y elements from the end of the array, such that the sum is maximum and x y = K.

That is a pretty simple problem to solve, which basically requires this algorithm:

ans = sum(last K elements)
for i in range(0, K):
    ans = max(ans, ans   array[i] - array[n-(k-i 1)]) #picking elements from the start and removing elements from the end