给定一个N个整数的堆栈，其中第一个元素代表堆栈的顶部，最后一个元素代表堆栈的底部。您需要从堆栈中弹出至少一个元素。在任何时候，您都可以将堆栈转换为队列。堆栈的底部表示队列的前面。不能将队列转换回堆栈。你的任务是精确地移除K个元素，使移除的K个元素的总和最大化。输出K个被删除元素的最大可能和M
输入:N=10, K=4
stack = [10 9 1 2 3 4 5 6 7 8]输出:34
说明:
从堆栈中弹出两个元素。即{10,9}
然后将堆栈转换为队列，并从队列中删除前2个元素队列中。也就是7{8}。
最大可能的和是10+9+8+7 = 34
我想用贪心算法解决它，代码如下:
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)
在正常的测试用例下(给定一个)它会工作，但在许多其他场景下它会失败，例如:
[10,9,1,30,3,4,5,100, 1,8]
有什么改进的建议吗?
数据结构让您可以选择1，…，从结构的停止处取n个值，然后从K = m+n的结构底部取m个元素。你可以通过对结构的前K个元素求和来找到最大值，然后用后面的第一个元素替换第n个元素。向后工作，你只能得到一个堆栈元素。记录沿途的最大值。
在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)
运行时间为O(n)。
如果你仔细看这个问题，它基本上可以归结为:
从数组的开头选择x元素，从数组的末尾选择y元素，使总和为最大值，x+y = K .
这是一个非常简单的问题，它基本上需要这个算法:
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
//C语言代码/*想法:
- W.K.即使它是堆栈或队列，我们也会在数组的末尾或开始执行pop/delete操作。我们正在利用这一点。2.K个元素必须从堆栈中移除，使它们的SUM为max
- 元素的弹出必须在堆栈的开始或结束，而不是。需要删除的元素中有一个是"K"。4.我们取K的所有可能性也就是说，如果我们从堆栈的前部取n个元素，那么从堆栈的后部取K-n个元素K = 5—>可能性:(0 5)(1 4)(2 3)(3 2)(4 1)(5 0)—>正如你可以观察到的，第一个索引增加到K，第二个索引从K衰减到0。(0 5)表示从堆栈的前面选择0个元素，从堆栈的后面选择5个元素同样，其他的可能性。
- 我们正在采取每种可能性并计算它们的总和，将它们存储在单独的数组' sum '中，并获得总和的最大值[]，这将是答案。当我们得到Max的可能性(假设a b)就是我们可以把堆栈转换成队列的时刻。在堆栈转换为堆栈之前，我们从堆栈中取出了一个元素，即数组的前面，在堆栈转换为队列之后，我们删除了b个元素，这将在队列的前面，即堆栈的后面完成。*/
输入图片描述