如何找到具有最大总和的递增数字子序列。我找到了O(N^2)的方法,但我想知道O(N log N)的方法。
谢谢!
谢谢!
我假设:
这会产生很大的差异!
解决方案
令数组 A
的最优递增子序列(IS)集合 S
为一组 IS,使得在 A
中的每个 IS s
,我们恰好有以下情况之一:
s
在 S 中s'
在 S
中,满足
sum(s')
>= sum(s)
,并且largest_element(s')
<= largest_element(s)
最优集合 S
可以按照子序列的最大元素和它们的总和进行排序 - 应该是相同的顺序。这就是我所说的稍后要讨论的最小/最大序列。
然后,我们的算法必须找到 A
的最优集合,并返回其最大序列。S 可以通过以下方式计算:
S := {[]} //Contains the empty subsequence
for each element x in A:
s_less := (largest sequence in S that ends in less than x)
s := Append x to s_less
s_more := (smallest sequence in S that has sum greater than s)
Remove all subsequences in S that are between s_less and s_more
(they are made obsolete by 's')
Add s to S
curr array | Optimal Subsequences
[] []
//best this we can do with 8 is a simgleton sequence:
[8] [] [8]
//The heaviest sequence we can make ending with 12 is [8,12] for a total of 20
//We still keep the [8] because a couble of 9s and 10s might make it better tahn 8+12
[8,12] [] [8] [8,12]
[8,12,11] [] [8] [8,11] [8,12]
[8,12,11,9] [] [8] [8,9] [8,11] [8,12]
//[8,9,10] makes [8,11] and [8,12] obsolete (remove those).
//It not only is heavier but the last number is smaller.
[8,12,11,9,10] [] [8] [8,9] [8,9,10]
1.) 对子序列进行排序
2.) 遍历您的列表,将下一个元素添加到前一个元素
3.) 一旦您达到两个元素的总和大于maximum_sum,请停止。之前的所有内容都可以结合在一起,<= maximum_sum。
这假设您要添加两个元素以使maximum_sum。一般概念可推广为0-N求和,其中N是“数字”的长度。但是,您没有明确说明要添加什么,因此我做了一个假设。另外,我不确定这是否会给您最长的数字子序列,但它将在N log N中为您提供数字子序列。
这是亚马逊公司在我第一轮面试时问我的问题,当时我因食物中毒而呕吐。我通过了第二轮面试,但他们似乎不想超越那一点。希望如果这是一个面试问题,您能做得比我更好,所以我的答案可能不是最好的,但希望它比说您有重复要好...
希望这有所帮助,
-Brian J. Stinar-