从头或尾部找到最大删除元素的总和？
给您一个n个整数的堆叠，使第一个元素代表堆栈的顶部，最后一个元素代表堆栈的底部。您需要从堆栈中至少弹出一个元素。在任何时候，您都可以将堆栈转换为队列。堆栈的底部表示队列的前部。您不能将队列转换回堆栈。您的任务是删除k元素，以使k删除元素的总和最大化。 打印k删除元件的最大可能总和m
输入：n = 10，k = 4
stack = [10 9 1 2 3 4 5 6 7 8]输出：34
说明：
从堆栈中弹出两个元素。即{10,9}
然后将堆栈转换为队列，然后从 队列。即{8,7}。
最大可能的总和是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]
关于如何改进的任何建议？
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
数据结构为您提供了从结构停止中选择1，...，n值的选项，然后是从k = m+n的结构底部的m元素。您可以通过总结结构的第一个k元素来找到最大值，然后通过从背面的第一个元素替换n'th元素来向后进行操作。向后工作，只能到达一个堆栈元素。跟踪一路上的最大值。
在Python中：
运行时间为O（n）。
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:
The running time is O(n).
如果您仔细查看问题，它基本上归结为：
从开始的开始和
x元素和y元素从数组的末端开始，因此总和是最大的和x+y = k。这是一个非常简单的问题，基本上需要此算法：
If you carefully look at the problem, it basically boils down to:
Select
xelements from the start andyelements from the end of the array, such that the sum is maximum andx+y = K.That is a pretty simple problem to solve, which basically requires this algorithm:
// C语言代码
/*
想法：
2.k必须在堆栈中删除k元素，以使它们的总和是最大元素
4.我们正在采取k的所有可能性
即，如果我们从堆栈的前部获取n个元素，则kn elements ahs到堆栈的后面选择
例如：k = 5 - ＆gt;可能性：
（0 5）（1 4）（2 3）（3 2）（4 1）（5 0） - ＆gt;正如您可以观察到的第一个INDX正在增加到K，第二个INDX从K中衰减到0。
（0 5）是指从堆栈的前面选择0个元素，从堆栈后面选择5个元素
同样，其他可能性。
*/
在此处输入图像描述
// code in C language
/*
Idea :
2.K elements has to be removed in a stack such that their SUM is max
4.We are taking all possibilities of K
i.e. if we take n elements from the front part of stack then K-n elements ahs to selected from back of stack
eg : K = 5 --> possibilities:
(0 5) (1 4) (2 3) (3 2) (4 1) (5 0) -->as you can observe first indx is increasing to K and second indx is decaying to 0 From K.
(0 5) means selecting 0 elements from front of stack and 5 elementts from back of stack
similarly, the other possibilities.
*/
enter image description here