algorithm - 使每个元素小于或等于 X 的最大和子数组

Question

给定一个包含 N 个整数的数组 A，我们需要找到子数组的最大总和，使得每个元素都小于或等于给定的整数 X

示例:设 N=8，数组为 [3 2 2 3 1 1 1 3]。现在如果 x=2 那么如果我们考虑 1 base indexing 则通过对 A[2] + A[3] 求和答案是 4。如何在 O(N) 或 O(N*logN) 中做这道题

目前我正在通过检查每个可能的子数组来使用 O(N^2) 方法。如何降低复杂度？

Answer 1

您可以利用这样一个事实:如果某个数组只包含小于或等于 X 的整数，那么它的所有子数组也都具有此属性。让我们为每个索引 i 找到子数组的最大可能总和，以 i (sub_sum) 结尾。

sub_sum[i] = 0, if array[i] > X
sub_sum[i] = max(array[i], sub_sum[i - 1] + array[i]), otherwise

初始条件是:

sub_sum[1] = 0, if array[1] > X
sub_sum[1] = max(array[1], 0), otherwise

您可以使用上面的公式在一个循环中计算所有 sub_sum 值。您问题的答案是 sub_sum 数组中的最大值。计算复杂度为O(n)。