MinRemovesOrdering

/* * Write a program that reads an array of integers and removes from it a minimal number of
 * elements in such way that the remaining array is sorted in increasing order.
 * Print the remaining sorted array. Example:
    {6, 1, 4, 3, 0, 3, 6, 4, 5}  {1, 3, 3, 4, 5}
 */
using System;
using System.Collections.Generic;
using System.Text;
using System.Threading.Tasks;

namespace _18.SortWithMinRemoves
{
    class SortWithMinRemoves
    {
        static bool CheckIfOrdered(List<int> arr)
        {
            bool isOrdered = true;
            for (int i = 0; i < arr.Count-1; i++)
            {
                if (arr[i]>arr[i+1])
                {
                    isOrdered = false;
                    break;
                }
            }
            return isOrdered;

        }
        static void Main(string[] args)
        {
            int[] arr = { 1,2,3,4,5,6,7,1,123,453,4674};
            List<int> list = new List<int>(arr.Length);
            int bitCounter = 0;
            int minRemoves = int.MaxValue;
            StringBuilder sb = new StringBuilder();
            int maxRotations = (int)Math.Pow(2, arr.Length) - 1;
            for (int i = 1; i < maxRotations; i++)
            {
                for (int p = 0; p < arr.Length; p++)
                {
                    int mask = 1 << p;
                    int m = i & mask;
                    int bit = m >> p;
                    if (bit == 1)
                    {
                        bitCounter++;
                    }
                    else
                    {
                        list.Add(arr[p]);
                    }
                }
                bool ordered = CheckIfOrdered(list);
                if (ordered)
                {
                    if (bitCounter<minRemoves)
                    {
                        sb.Clear();
                        minRemoves = bitCounter;
                        for (int j = 0; j < list.Count; j++)
                        {
                            sb.Append(list[j] + " ");
                        }
                    }
                }
                bitCounter = 0;
                list.Clear();
            }
            Console.WriteLine(sb);
        }
    }
}