배열 A의 임의의 배열요소 A[i]에 대해 최대 증가 시퀀스는 먼저 A[0] 부터 A[i-1]까지의 배열 요소 A[j](0 <=j < i) 중에 A[j]값이 A[i]값 보다 적은 배열요소를 선별한다. 이렇게 선별된 A[j] 들 중에 최대 시퀀스를 갖는 A[j] 시퀀스 사이즈에 1을 더해 A[i]의 최대 시퀀스 사이즈를 구한다.

static void Main(string[] args)  
{      
         int[] nums = { 2, 6, 4, 5, 1, 3 };    // LIS = 2,4,5     
         GetMaxLIS(nums);  
}    

static void GetMaxLIS(int[] A)  
{      
       int max = 0;      
       int[] LS = new int[A.Length];                    
       for (int i = 0; i < A.Length; i++)      
       {          
            // init          
            LS[i] = 1;            

            // LS[i] = Max{ LS[j] } + 1 where A[i] > A[j]          
            for (int j = 0; j < i; j++)          
            {             
                  if (A[i] > A[j] &&        
                      LS[i] < LS[j] + 1)              
                 {                  
                      LS[i] = LS[j] + 1;              
                  }
             }  
             Console.WriteLine("LS[{0}]={1}", i, LS[i]);   

            // set total max          
            max = Math.Max(max, LS[i]);      
        }

        Console.WriteLine("Max LIS = " + max);  
}