Problem:
Let a mirror be a contiguous group of elements in an array such that somewhere in the array the same group appears in reverse order. For example, the largest mirror section in {1,2,3,8,9,3,2,1} is length 3 (the {1,2,3} part). Write a function that will return the length of the biggest mirror in the array.
Solution:
[show_more more=”View solution” less=”Close solution”]
A way to accomplish this is to visit every number in the array once. At each number we check the entire array to see if we can find it at another spot and work forward from our first index and backward from where we find the second instance of the number comparing each number at that spot and increasing our total size each time the numbers are equal to each other. When they are not we return the size we got compare it to what our current maximum is and replace it if it is bigger. We also know that the maximum size cannot be greater than floor(n/2) so we can stop if the max size reaches that value.
[csharp]
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
namespace Pessetto
{
public class Program
{
public static void Main(string[] args)
{
int noTestCases = Int32.Parse(Console.ReadLine());
for(int i = 0; i < noTestCases; ++i)
{
int caseSize = Int32.Parse(Console.ReadLine());
int[] workingArray = new int[caseSize];
for(int j = 0; j < caseSize; ++j)
{
workingArray[j] = Int32.Parse(Console.ReadLine());
}
Console.WriteLine(MaxMirror(ref workingArray));
}
}
public static int MaxMirror(ref int[] values)
{
int maxValue = 0;
for(int i = 0; i < values.Length && maxValue <= values.Length/2; ++i) { int currentValue = MaxOfCurrentIndex(i,ref values); if(currentValue > maxValue)
{
maxValue = currentValue;
}
}
return maxValue;
}
public static int MaxOfCurrentIndex(int index, ref int[] values)
{
int max = 0;
for(int i = values.Length – 1; i >= index && max < values.Length; –i) { if(values[i] == values[index]) { var mirrorLength = GetCurrentMirrorLength(index,i,ref values); if(mirrorLength > max)
{
max = mirrorLength;
}
}
}
return max;
}
public static int GetCurrentMirrorLength(int firstIndex, int searchIndex, ref int[] values)
{
int length = 0;
int firstIndexPlaceholder = firstIndex;
while(searchIndex >= firstIndexPlaceholder && values[firstIndex] == values[searchIndex])
{
++length;
–searchIndex;
++firstIndex;
}
return length;
}
}
}
[/csharp]
Play with the solution online.
[/show_more]