algorithm - 找到所有子数组的最大子数组

Question

给定一个二进制数组（元素为 0 或 1），我需要找到数组中给定范围（l 和 r）全为 1 的子数组的最大长度。

我知道查找此类子数组的 O(n) 方法，但如果有 O(n) 查询，则整体复杂性变为 O(n^2)。

我知道段树用于此类问题，但我不知道如何为这个问题构建树。

我是否可以构建一个分段树，使用它可以在 log(n) 时间内回答查询，这样对于 O(n) 查询的整体复杂性将变为 O(nlog(n))。

标签： algorithmdata-structuressegment-tree

Answer 1

让A成为你的二进制数组。
构建两个数组IL和IR：
-IL按顺序包含每个i这样的A[i] = 1 and (i = 0 or A[i-1] = 0);
-IR按顺序包含每一个i这样的A[i-1] = 1 and (i = N or A[i] = 0)。

换句话说，对于任何i，由IL[i]包含和IR[i]不包含定义的范围对应于 中的1s序列A。

现在，对于任何查询{L, R}（对于范围 [L; R] 包括在内），让S = 0. 遍历IL和IR，i直到IL[i] >= L。此时，如果IR[i-1] > L，设置S = IR[i-1]-L。继续遍历IL和IR，设置S = max(S, IR[i]-IL[i])，直到IR[i] > R。最后，如果IL[i] <= R，设置S = max(S, R-IL[i])。

S现在是 和 之间的最大s序列1的大小。ALR

构建IL和的复杂度IR是O(N)，回答查询的复杂度是O(M)，M长度为ILor IR。