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

Question

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

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

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

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

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]非包含对应于 1 的序列在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现在是 1 的最大序列的大小在A在 L 之间和 R .

建筑的复杂性IL和 IR是O(N) ，回答查询的复杂度是 O(M) , 与 M IL 的长度或 IR .