public class Solution {
    public int MaxSubArray(int[] nums)
    {
        if(nums.Length == 1)
        {
            return nums[0];
        }
        else if(nums.Length == 0)
        {
            return Int32.MinValue;
        }
        else
        {
            int mid = nums.Length/2;
            int Left = MaxSubArray(ArraySlice(nums, 0, mid));
            int Right = MaxSubArray(ArraySlice(nums, mid+1, nums.Length));
            int Cross = MaxCross(nums, mid);
            if((Left > Right)&&(Left > Cross))
            {
               return Left;
            }
            else if(Right > Cross)
            {
                return Right;
            }
            else
            {
                return Cross;
            }
        }
    }
    public int[] ArraySlice(int[] nums, int start,  int end)
    {
        if(end < 0)
        {
            end = nums.Length + end;
        }
        int len = end - start;
        int[] newArray = new int[len];
        for(int i = 0; i < len; i++)
        {
            newArray[i] = nums[i+start];
        }
        return newArray;
    }
    public int MaxCross(int[] nums, int mid)
    {
        int leftSum = nums[mid];
        int sum = 0;
        for(int i = mid; i >= 0; i--)
        {
            sum += nums[i];
            if(sum > leftSum)
            {
                leftSum = sum;
            }
        }
        int rightSum = 0;
        sum = 0;
        for(int i = mid+1; i < nums.Length; i++)
        {
            sum += nums[i];
            if(sum > rightSum)
            {
                rightSum = sum;
            }
        }
        Console.WriteLine("Right sum is {0}", rightSum);
        Console.WriteLine("Left sum is {0}", leftSum);
        return leftSum + rightSum;
    }
}