查找不同数字的最大连续子数组求和

Question

在给定数组中查找带有不同数字的最大连续子数组和。如果在任何子阵列中存在至少两个相等的数字，则该数字的值等于0.

所有数字都是正数。

我写了O（n²）蛮力算法，但它肯定太慢了。 我试图用Kadane的算法来混合它，但似乎并不奏效。

Answer 1

使用分段树可以获得时间复杂度O(n log n)。

1. 让我们假设答案的左边框（我们称之为L）是固定的。从左边的所有东西都可以忽略。数组其余部分的每个元素可以表示为：
   a）+x如果它是第一次出现x。
   b）-x如果它是第二次出现x。
   c）0如果它是第三次（或更晚）发生的x,
   其中x = a[i]。
   然后答案是所有子阵列的最大子阵列总数[L, R]其中R >= L。

2. 那么如何有效实施？最初，为[0, n - 1]范围构建分段树。段树中的每个叶子都包含前缀总和，该总和始于L，并以此叶子结尾（到目前为止为0）。填写它为L = 0（通过遍历整个阵列，并添加+x或-x适当的足够的分段树）。这些部分在O(n log n)中工作。还有一种观察：当L增加时，该值仅在最多3个位置上变化（因为a[L]的第一次出现现在处于另一个位置，但其他数字没有变化）。分段树中的每个更新为O(log n)，因此需要O(log n)时间来增加L一次。总时间复杂度为O(n log n)，因为L递增O(n)次。不要忘记查询分段树，以获得每个L的最大值，并选择最大的值作为答案。

因此，所有你需要的是一个支持两种操作的段树：添加相同数量的所有元素在给定的范围内，并得到所有元素中最高。这是一个众所周知的问题，并不是很难实施。