/*
 * 找出数组中最大子序列之和，分别以O(N^2),O(NlogN),O(N) 这3种时间复杂度求解
 */

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

namespace MaxSubSumPro
{
    class ArrayFactory
    {
        public static int[] RandomIntArray(int length)
        {
            return RandomIntArray(length, -1000, 999);
        }

        public static int[] RandomIntArray(int length, int minValue, int maxValue)
        {
            if (length <= 0 || minValue >= maxValue)
            {
                throw new ArgumentOutOfRangeException();
            }
            Random ran = new Random(minValue + (maxValue - minValue) / 1000 * DateTime.Now.Millisecond);
            int[] arr = new int[length];
            for (int i = 0; i < length; ++i)
            {
                arr[i] = ran.Next(minValue, maxValue);
            }
            return arr;
        }
    }

    class Printer<T>
    {
        public static void PrintArray(T[] array)
        {
            PrintArray(array, 10);
        }

        public static void PrintArray(T[] array, int maxItemInLine)
        {
            int temp = 0;
            for (int i = 0; i < array.Length; ++i)
            {
                Console.Write("{0,10} ", array[i].ToString());
                ++temp;
                if (temp == maxItemInLine)
                {
                    Console.WriteLine();
                    temp = 0;
                }
            }
        }
    }

    class MaxSubSum
    {
        /// <summary>
        /// O(N^2)
        /// </summary>
        /// <param name="array"></param>
        /// <returns></returns>
        public static long MaxSubSum1(int[] array)
        {
            long maxSum = Check(array);
            if (maxSum > 0)
            {
                maxSum = 0L;
                long sum;
                for (int i = 0; i < array.Length; ++i)
                {
                    sum = 0L;
                    for (int j = i; j < array.Length; ++j)
                    {
                        sum += array[j];
                        if (sum > maxSum)
                        {
                            maxSum = sum;
                        }
                    }
                }
            }
            Console.WriteLine("MaxSubSum1 output:" + maxSum);
            return maxSum;
        }

        /// <summary>
        /// O(NlogN)
        /// </summary>
        /// <param name="array"></param>
        /// <returns></returns>
        public static long MaxSubSum2(int[] array)
        {
            long maxSum = Check(array);
            if (maxSum > 0)
            {
                maxSum = MaxSubSum2_Recursion(array, 0, array.Length - 1);
            }
            Console.WriteLine("MaxSubSum2 output:" + maxSum);
            return maxSum;
        }

        private static long MaxSubSum2_Recursion(int[] array, int left, int right)
        {
            if (left == right)
            {
                return array[left];
            }

            int mid = (left + right) / 2;
            long maxSumLeft = MaxSubSum2_Recursion(array, left, mid);
            long maxSumRight = MaxSubSum2_Recursion(array, mid + 1, right);
            long maxSumLeft_RightEdge = 0L;
            long maxSumRight_LeftEdge = 0L;

            long sum = 0L;
            for (int i = mid; i > left; --i)
            {
                sum += array[i];
                if (sum > maxSumLeft_RightEdge)
                {
                    maxSumLeft_RightEdge = sum;
                }
            }
            sum = 0L;
            for (int i = mid + 1; i < right; ++i)
            {
                sum += array[i];
                if (sum > maxSumRight_LeftEdge)
                {
                    maxSumRight_Left