查找不同數字的最大連續子數組求和

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的最大值，並選擇最大的值作爲答案。

因此，所有你需要的是一個支持兩種操作的段樹：添加相同數量的所有元素在給定的範圍內，並得到所有元素中最高。這是一個衆所周知的問題，並不是很難實施。