最长的正和子串

Question

我想知道如何在序列中得到最长的正和子序列:

例如,我有-6 3 -4 4 -5,所以最长的正子序列是3 -4 4.实际上总和是正数(3),我们不能加-6而不是-5或者它会变成负.

它可以很容易地在O(N ^ 2)中解决,我认为可以存在更快的东西,就像O(NlogN)

你有什么主意吗？

编辑:必须保留订单,您可以跳过子字符串中的任何数字

EDIT2:如果我使用术语"sebsequence"引起混淆,我很抱歉,因为@beaker指出我的意思是子串

Answer 1

让我们先进行一个简单的实现，然后改进它。

\n\n

我们从左向右计算部分和，对于每个位置，我们发现最左边的部分和，例如当前的部分和大于该位置。

\n\n

input a\nint partialSums[len(a)]\nfor i in range(len(a)):\n    partialSums[i] = (i == 0 ? 0 : partialSums[i - 1]) + a[i]\n    if partialSums[i] > 0:\n        answer = max(answer, i + 1)\n    else:\n        for j in range(i):\n            if partialSums[i] - partialSums[j] > 0:\n                answer = max(answer, i - j)\n                break\n

\n\n

这是 O(n ² )。现在，找到最左边的“好”总和的部分实际上可以通过BST来维护，其中每个节点将表示为一对(partial sum, index)，并通过 进行比较partial sum。此外，每个节点都应该支持一个特殊字段，min该字段是最小的indices。

\n\n

现在，我们可以使用当前的部分和作为关键字，遵循接下来的三个规则（假设C是当前节点，L并且R分别是左子树和右子树的根），而不是直接搜索适当的部分和：

\n\n

\n
1. curMin最初维持在 中找到的“良好”部分和的当前最小索引+\xe2\x88\x9e。
\n
2. 如果C.partial_sum是“好”，则更新curMin为C.index。
\n
3. 如果我们去R然后curMin更新L.min。
\n

\n\n

然后更新answer为i - curMin并将当前的部分和添加到 BST 中。

\n\n

这将给我们 O(n * log n)。

\n