I have a difficulty in trying to solve this following algorithm problem. Given a

Question

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:

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.

Explanation / Answer

#include <stdio.h>

int main(void) {
   // your code goes here
  
   n = len(A)
ctr = 0
min = 0
max = 0
leftIndex = 1
rightIndex = 1
   ans = 0
for i in range(n):
if A[i] == X:
ctr = ctr + 1
else:
ctr = ctr - 1
if ctr > max:
max = ctr
leftIndex = i
if ctr < min:
min = ctr
rightIndex = i
ans = max_count - min_count
if leftIndex > rightIndex: # swap the two indices
temp = leftIndex
leftIndex = rightIndex
rightIndex = temp
leftIndex = leftIndex + 1
return (ans, leftIndex, rightIndex)
  
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.