Tech Qu: Maximum sub sequence which has equal number of 1s and 0s.

You are given an array ' containing 0s and 1s. Find the maximum sub sequence which has equal number of 1s and 0s.

 

The solution is straight forward (using a long  so testing would be easy).

• We determine the maximum possible length and use this to shorten the loops.
  

Code Snippet

1. public static int Subsequence(long rawdata)
2.     {
3.       var data = new BitArray(System.BitConverter.GetBytes(rawdata));
4.       if (data.Length < 2)
5.         return data.Length;
6.       var zCount = 0;
7.       var oneCount = 0;
8.       var sb = new StringBuilder();
9.       foreach (bool datum in data)
10.       {
11.         if (datum)
12.         {
13.           oneCount++;
14.           sb.Append("1");
15.         }
16.         else
17.         {
18.           zCount++;
19.           sb.Append("0");
20.         }
21.       }
22.       var endSearch =2 * Math.Min(oneCount, zCount);
23.       var maxlength = 0;
24.       var index = 0;
25.       for (int i = 0; i < data.Length; i++)
26.       {
27.         var count = 0;
28.         for (int j = i; j < Math.Min( i + endSearch,data.Length); j++)
29.         {
30.           count += data[j] ? 1 : -1;
31.           if (count == 0 &&  maxlength < j-i)
32.           {
33.             maxlength = j - i +1;
34.             index = j;
35.           }
36.         }
37.       }
38.       Console.WriteLine(String.Format("{0}:{1} --> {2}",
39.       rawdata,
40.       sb,
41.       maxlength));
42.       return maxlength;
43.     }

The test was done by just walking values and spot checking.

Code Snippet

1. for(long i=1; i < 32; i++)
2. {
3.   Questions.Subsequence(i);
4. }

Resulting in this output.

 

The example for 17, yielding just 2 appears to confirm correctness.