algorithm - 如何找到最大和的递增数字子序列？

Question

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

谢谢!

Answer 1

我假设:

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

这让世界变得不同!

---

解决方案

令数组 A 的递增子序列 (IS) 的最佳集合 S 是一组 IS，使得每个 IS s 在A 我们正好有以下之一:

• s 在 S 中
• S 中有一个 IS 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

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]