Elm*_*dov 5 algorithm dynamic-programming
如何找到具有最大总和的数字的增加子序列.我找到O(N ^ 2)但我想知道O(N log N).
谢谢!
1.) 对子序列进行排序
2.) 迭代列表，将下一个元素添加到上一个元素
3.) 一旦到达两个元素的和大于maximum_sum，就停止。前面的所有内容都可以组合在一起<=maximum_sum。
这假设您要求添加两个元素以得到maximum_sum。一般概念可以推广为 0-N 求和，其中 N 是“数字”的长度。然而，你并没有澄清你实际上加在一起的内容，所以我做了一个假设。另外，我不确定这是否会给你“最长”的数字子序列，但它会给你一个 N log N 的数字子序列。
这是亚马逊在第一轮面试中因食物中毒而呕吐时问我的面试问题。我进入了第二轮面试，但他们似乎不想再继续下去了。如果这是一个面试问题，希望你能比我做得更好，所以我的答案可能不是最好的，但希望这比说你有重复的要好......
希望这有帮助，
-布莱恩·J·斯蒂纳尔-