Max Common Array Slice in C#

You are given a sequence of n integers a0, a1, . . . , an−1 and the task is to find the maximum slice of the array which contains no more than two different numbers.

Input 1 :

[1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 6, 2, 1, 8]

Result 1 : Answer is 10 because the array slice of (0, 9) is the largest slice of the array with no more than two different numbers.

- There are 10 items in this slice which are "1, 1, 1, 2, 2, 2, 1, 1, 2, 2".
- 2 different numbers for this slice are 1 and 2.


Input 2:

[53, 800, 0, 0, 0, 356, 8988, 1, 1]

Result 2: Answer is 4 because the slice of (1, 4) is the largest slice of the array with no more than two different numbers. The slice (2, 5) would also be valid and would still give a result of 4.

- There are 4 items in this slice which are "800,0,0,0".
- 2 different numbers for this slice are 800 and 0.

Maximum common array slice of the array which contains no more than two different numbers implementation in C# takes a comma delimited array of numbers from STDIN and the output is written back to console.

Important thing here is that the usage of the Dictionary data structure from "System.Collections.Generic" namespace.

Sample implementation uses Add, ContainsKey and Clear methods of the Dictionary class of the .Net framework.

using System;
using System.Collections.Generic;
using System.Text.RegularExpressions;

namespace MaxCommonArraySlice
{
    class Program
    {

        public static int maxCommonArraySlice(int[] array)
        {
            Dictionary<int, int> items = new Dictionary<int, int>();
            int result = 0;
            int startIndex = 0;
            int uniqueItemCount = 0;
            while (startIndex < array.Length)
            {
                items.Add(array[startIndex], startIndex);
                uniqueItemCount = uniqueItemCount + 1;
                for (int j = startIndex + 1; j < array.Length; j++)
                {
                    if (items.ContainsKey(array[j]) == false)
                    {
                        if (uniqueItemCount != 2)
                        {
                            items.Add(array[j], j);
                            uniqueItemCount = uniqueItemCount + 1;
                            if (j == array.Length - 1)
                            {
                                result = Math.Max(result, j - startIndex + 1);
                                startIndex = array.Length;
                                break;
                            }
                        }
                        else if (uniqueItemCount == 2)
                        {
                            result = Math.Max(result, j - startIndex);
                            int item = array[j - 1];
                            int firstFoundIndex = 0;
                            for (int k = j - 1; k >= 0; k--)
                            {
                                if (array[k] != item)
                                {
                                    firstFoundIndex = k + 1;
                                    break;
                                }
                            }
                            startIndex = firstFoundIndex;
                            items.Clear();
                            uniqueItemCount = 0;
                            break;
                        }
                    }
                    else if (items.ContainsKey(array[j]) != false)
                    {
                        if (j == array.Length - 1)
                        {
                            result = Math.Max(result, j - startIndex + 1);
                            startIndex = array.Length;
                            break;
                        }
                    }
                }
            }

            return result;
        }

        static void Main(string[] args)
        {

            string line = Console.ReadLine();
            if (!line.Equals(""))
            {
                if (line.Length == 1)
                {
                    Console.WriteLine("1");
                }
                else
                {
                    try
                    {
                        line = Regex.Replace(line, @"\s+", "");
                        String[] items = line.Split(',');
                        int N = items.Length;
                        int[] input = new int[N];

                        for (int i = 0; i < N; i++)
                            input[i] = Int32.Parse(items[i]);

                        if (input.Length == 1)
                        {
                            Console.WriteLine("1");
                        }
                        else
                        {
                            int result1 = maxCommonArraySlice(input);
                            Console.WriteLine(result1);
                        }
                    }
                    catch (Exception ex)
                    {
                        Console.WriteLine(ex.ToString());
                    }
                }
            }
        }
    }
}

When you create a new Program.cs file and put the above code inside it with a Main() method, application waits you to enter some input from the console.

Following is the console input and output :

Another console input and output of the above program :

Another console input and output of the above program :

Another console input and output of the above program :

Another console input and output of the above program :