arrays - 查找元素数量差异最大的子数组

Question

我在尝试解决以下算法问题时遇到了困难。
给定一个数组 A[1 ... N]，其中每个 A[i] 要么是 X 要么是 Y。找到一个连续的子数组 A[i..j]，其中 X 和 Y 之间的绝对差最大。
例如，在数组 A=[X, X, Y, Y, X, Y, Y, X, Y, X ] 中，最大绝对差值是子数组 A[3 .. 7]，因为我们有 3 个 Y 和1 X(数组A的索引从1开始)。
再比如，如果我们的数组 A=[X, X, Y, X, X, Y, Y, X]，那么最大绝对差就是子数组 A[1 .. 5]。
给出一个简单的算法来解决这个问题。分析算法的运行时间。

下面是我创建的算法:

MAX-DIF-SUBARRAY(A, n)
dif_now = 0
dif_new = 0
left = 0    # the lowest index
right = 0   # the highest index
for i=2 to n
   for j=1 to n+1-i
      Xcount, Ycount = 0
      for k=j to j+i-1
         if A[k] = X
            Xcount = Xcount + 1
         else Ycount = Ycount + 1
      dif_new = |Xcount - Ycount|
      if dif_new > dif_now
         dif_now = dif_new
         left = k
         right = j+i-1
return dif_now, left, right. 

这个算法需要时间 O(n^3)。
谁能帮我找到一个可以在 O(n^2) 中运行的更好的算法？另外，如何制作这个算法的递归版本？
先感谢您。

Answer 1

您可以在线性时间内完成此操作，方法是遍历数组一次，并保留一个总和，当您遇到 X 时该总和会递增，而当您遇到 Y 时该总和会递减。在这样做的同时还要跟踪该总和在哪些索引处达到它的值最小值和最大值。

这为您提供了两个索引。这两个中最小的加上 1 是子数组的开始，另一个索引标记该子数组中的最后一个元素。最大化的差值是上述过程中记录的最小值和最大值之间的差值。

伪代码:

MAX-DIF-SUBARRAY(A):
    n = size(A)
    count = 0
    min_count = 0
    max_count = 0 
    left = 1
    right = 1

    for i=1 to n:
        if A[i] == X:
            count = count + 1
        else
            count = count - 1
        if count > max_count:
            max_count = count
            left = i
        if count < min_count:
            min_count = count
            right = i
    dif = max_count - min_count
    if left > right: # swap the two indices
        temp = left
        left = right
        right = temp
    left = left + 1
    return dif, left, right