using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication10
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] intArr = { 8,2,5,9,4,1,3,7,-1};
            MaxMin result = FindMaxAndMin(intArr, 0, intArr.Length - 1);
            Console.WriteLine("max is {0}, min is {1}",result.max, result.min);
        }

        static MaxMin FindMaxAndMin(int[] input, int start, int end)
        {
            MaxMin result;
            if (end - start <=1)
            {
                if (input[start]>input[end])
                {
                    result.max = input[start];
                    result.min = input[end];
                }
                else
                {
                    result.max = input[end];
                    result.min = input[start];
                }
                return result;
            }

            MaxMin front = FindMaxAndMin(input, start, start + (end - start) / 2);
            MaxMin rear = FindMaxAndMin(input, start + (end - start) / 2 + 1, end);

            if (front.max > rear.max)
            {
                result.max = front.max;
            }
            else
            {
                result.max = rear.max;
            }

            if (front.min<rear.min)
            {
                result.min = front.min;
            }
            else
            {
                result.min = rear.min;
            }

            return result;

        }
    }

    struct MaxMin
    {
        public int max;
        public int min;
    }
}