使用括号查找加/减的最大值
使用括号查找加/减的最大值
提问于 2015-11-10 04:42:27
给定一系列相加和相减的数字(例如，4-3-5)，如何插入括号以找到最大值？在我的示例中，4-3-5可以是：
(4-3)-5 = -4或
4-(3-5) = +6
所以第二个结果是最大值。但是，对于像4+5-8-6-3-2这样的东西，暴力方法将花费太长的时间。
如何找到最大值？我认为动态编程可能对解决这个问题很有用。
回答 1
Stack Overflow用户
发布于 2015-11-10 09:53:56
动态编程确实是正确的。您需要的是一对函数。其中一个告诉你，给定一个数字区间，在哪里除以得到最大值，以及你得到的最大值是多少。另一个做同样的事情以得到最小值。
这两个函数都可以通过尝试将每个点分成两部分来递归计算，并查看它导致的结果。具体地说，如果你正在寻找一个最大值并在-上除以，你想要使前半个最大，第二个最小。如果你正在寻找一个最大值并且除以一个+，你想要两个一半都是最大值。如果你正在寻找一个最小值，并且除以一个+，你想要两个一半都是最小值。如果你正在寻找一个最小值并在-上除以，你需要前半个分钟和第二个最大值。
为了提高效率，您可以对每个函数进行记忆。现在它应该在time O(n^3)中运行。(您必须计算每个O(n^2)间隔，并且每个计算都涉及查找O(n)可能的分割点。)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/33617888
复制相关文章
相似问题
腾讯云开发者
