CODEWITHSUNDEEP
arraysalgorithmrecursionmaxarray-difference
mskeira
mskeira

Reputation: 25

Finding the subarray that has the maximum difference in the number of elements

I have a difficulty in trying to solve this following algorithm problem.
Given an array A[1 ... N], where each A[i] is either X or Y. Find a contiguous subarray A[i..j], where the absolute difference between X and Y is maximized.
For example, in array A=[X, X, Y, Y, X, Y, Y, X, Y, X ], the maximum absolute difference is the subarray A[3 .. 7], because we have 3 Y and 1 X (the index of the array A starts from 1).
Another example, if our array A=[X, X, Y, X, X, Y, Y, X], then the maximum absolute difference is the subarray A[1 .. 5].
Give a simple algorithm to solve this problem. Analyze the running time of the algorithm.

Below is the algorithm that I created:

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.

This algorithm takes time O(n^3).
Could anyone please help me to find a better algorithm that can run in O(n^2)? Also, how to make the recursive version of this algorithm?
Thank you in advance.

Upvotes: 0

Views: 1267

Answers (1)

trincot
trincot

Reputation: 351218

You could do this in linear time, by going over the array once, and keeping a sum which you increment when you encounter X, and decrease when you encounter Y. While doing so also keep track at which indices this sum reaches its minimum value and maximum value.

This gives you two indices. The least of these two, plus 1, is the start of the sub array, and the other index marks the last element in that sub array. The difference that was maximised is the difference between the minimum and maximum value that were recorded during the above process.

Pseudo code:

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

Upvotes: 1

Related Questions