public class Solution {
    public int MaxSubArray(int[] nums) {
        if(nums.Length == 1)
        {
            return nums[0];
        }
        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 > Left)&&(Right > Cross))
            {
                return Right;
            }
            else
            {
                return Cross;
            }
            return 1;
        }
    }
    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 = Int32.MinValue;
        int sum = 0;
        for(int i = mid; i > 0; i--)
        {
            sum += nums[i];
            if(sum > leftSum)
            {
                leftSum = sum;
            }
        }
        int rightSum = Int32.MinValue;
        sum = 0;
        for(int i = mid + 1; i < nums.Length; i++)
        {
            sum += nums[i];
            if(sum > rightSum)
            {
                rightSum = sum;
            }
        }
        return leftSum + rightSum;
    }
}