如何找到总和最大的递增子序列？

Question

如何找到具有最大和的数字的递增子序列。 我找到 O(N^2) 但我想知道 O(N log N)。

谢谢！

Answer 1

我假设：

• 您根本不关心子序列的长度。
• 子序列不需要是连续的

这使得世界变得不同！

---

解决方案

设数组 A 的递增子序列 (IS) 的最佳集合 S 为一组 IS，使得每个 IS 在 A 中，我们恰好有以下之一：

• 在 S 中的 s
• 在 S 中有一个 IS s'代码>这样
  • sum(s') >= sum(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

S 中最大的子序列是数组中最大的子序列。

每个步骤都可以在 O(log n) 内实现，因为 S 是平衡二叉树。 n 个步骤的总复杂度为 O(n*log n)。

警告：我的伪代码中很可能存在一些 +- 1 错误 - 找到它们作为读者的练习:)

---

我将尝试给出一个具体示例。也许这有助于使这个想法更清晰。
最右边的子序列始终是迄今为止最好的序列，但其他序列是因为将来它们可能会成为最重的序列。

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]

Answer 2

扫描阵列。维护一个展开树，将每个元素 x 映射到以 x 结尾的子序列的最大和。这棵展开树按x（不是x的索引）排序，每个节点都用子树最大值装饰。最初，树只包含一个哨兵 Infinity => 0. 要处理新值 y，请在树中搜索最左边的值 z，使得 y <= z。将 z 展开到根。 z 左孩子的子树 max M 是 y 可以扩展的子序列的最大和。将 (y, M + y) 插入树中。最后，返回树最大值。

Answer 3

1.) 对子序列进行排序

2.) 迭代列表，将下一个元素添加到前一个元素

3.) 一旦到达两个总和大于 Maximum_sum 的元素，就停止。前面的所有内容都可以组合在一起，小于等于maximum_sum。

这假设您要求添加两个元素以得到maximum_sum。一般概念可以推广为 0-N 求和，其中 N 是“数字”的长度。然而，你并没有澄清你实际上加在一起的内容，所以我做了一个假设。另外，我不确定这是否会给你“最长”的数字子序列，但它会给你 N log N 中的数字子序列。

这是亚马逊在我呕吐时问我的一个面试问题在第一轮采访中摆脱食物中毒。我进入了第二轮面试，但他们似乎不想再继续下去了。如果这是一个面试问题，希望你能比我做得更好，所以我的答案可能不是最好的，但希望它比说你有重复的更好......

希望这有帮助，

-Brian J. Stinar-

Answer 4

我在 codeforces 上遇到了类似的问题。该问题可以使用带有坐标压缩的线段树或使用平衡二叉搜索树来完成。请参阅以下链接以获取详细说明。

最大和递增序列

看完之后你可以尝试一下关于 codeforces 的这个问题。