利用分治算法在未排序数组中寻找最大和
利用分治算法在未排序数组中寻找最大和
提问于 2016-09-12 07:49:04
我有一个由n个实数组成的序列存储在一个数组中，A1，A2，…、An.我正在尝试实现一个分而治之的算法来找到两个数字Ai和Aj，其中i< j，使得Ai≤Aj和它们的和是最大的。
例如。{2，5，9，3，-2，7}将输出14 (5+9，而不是16=9+7)。有没有人能给我一些建议？
提前谢谢。
回答 4
Stack Overflow用户
发布于 2016-09-12 12:24:18
这个问题并不真正适合分而治之的方法。
很容易观察到，如果(i，j)是这个问题的解，那么对于每个k> j，Aj >= Ak，即Aj是Aj中的最大值。
证明:如果存在k>j且Ak > Aj，则(j，k)是比(i，j)更好的解
因此，我们只需要考虑满足该条件的j。
算法(伪代码)
maxj = n
for (j = n - 1 down to 1):
if (a[j] > a[maxj]) then:
maxj = j
else:
check if (j, maxj) is a better solution复杂度: O(n)
C++实现：http://ideone.com/ENp5WR (该实现使用整数数组，但对于浮点数应该是相同的)
Stack Overflow用户
发布于 2016-09-12 07:57:21
声明两个变量，在你的算法中检查当前数是否大于当前存储在变量中的两个值中的任何一个，如果是，则替换最小的值，如果不是，则继续。
Stack Overflow用户
发布于 2016-09-12 08:24:49
这是一个用Python编写的递归解决方案。我不会确切地称之为“分而治之”，但话又说回来，这个问题不太适合分而治之的方法。
def recurse(lst, pair): # the remaining list left to process
if not lst: return # if lst is empty, return
for i in lst[1:]: # for each elements in lst starting from index 1
curr_sum = lst[0] + i
if lst[0] < i and curr_sum > pair[0]+pair[1]: # if the first value is less than the second and curr_sum is greater than the max sum so far
pair[0] = lst[0]
pair[1] = i # update pair to contain the new pair of values that give the max sum
recurse(lst[1:], pair) # recurse on the sub list from index 1 to the end
def find_pair(s):
if len(s) < 2: return s[0]
pair = [s[0],s[1]] # initialises pair array
recurse(s, pair) # passed by reference
return pair示例输出：
s = [2, 5, 9, 3, -2, 7]
find_pair(s) # ============> (5,9) 页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/39441748
复制相关文章
相似问题
腾讯云开发者
