二部图问题

using System;



namespace csdnTest

{

    class Program

    {

        static void Main(string[] args)

        {

            int[] items = new int[] { 4, 2, 6, 3, 1, 2, 5 };



            //用来记录序列长队最大值的数组，index + 1就是序列的长度

            int[] maxValues = new int[items.Length];

            int maxLength = 1;

            maxValues[0] = items[0];



            for (int i = 1; i < items.Length; i++)

            {

                //二分查找对应的最长序列

                int lengthIndex = Array.BinarySearch<int>(maxValues, 0, maxLength, items[i]);

                

                //针对于.Net里面的BinarySearch的特殊处理，不用理会

                if (lengthIndex < 0) 

                    lengthIndex = -lengthIndex - 1;



                if (lengthIndex + 1 > maxLength)

                    maxLength = lengthIndex + 1;



                maxValues[lengthIndex] = items[i];

            }



            Console.WriteLine(maxLength);

        }

    }

}