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

/*
 * 找出数组中最大子序列之和，分别以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_LeftEdge = sum;
                }
            }

            return Max3(maxSumLeft, maxSumRight, maxSumLeft_RightEdge + maxSumRight_LeftEdge);
        }

        private static long Max3(long a, long b, long c)
        {
            long r = a > b ? a : b;
            return r > c ? r : c;
        }

        /// <summary>
        /// O(N)
        /// </summary>
        /// <param name="array"></param>
        /// <returns></returns>
        public static long MaxSubSum3(int[] array)
        {
            long maxSum = Check(array);
            if (maxSum > 0)
            {
                maxSum = 0L;

                long sum = 0L;
                for (int i = 0; i < array.Length; ++i)
                {
                    sum += array[i];
                    if (sum > maxSum)
                    {
                        maxSum = sum;
                    }
                    else if (sum < 0)
                    {
                        sum = 0;
                    }
                }
            }
            Console.WriteLine("MaxSubSum3 output:" + maxSum);
            return maxSum;
        }

        private static int Check(int[] array)
        {
            if (array == null)
            {
                throw new ArgumentNullException("array");
            }
            else if (array.Length == 0)
            {
                throw new ArgumentException("array has no items");
            }
            else
            {
                int max = array[0];
                foreach (int item in array)
                {
                    if (max > 0)
                    {
                        break;
                    }
                    if (item > max)
                    {
                        max = item;
                    }
                }
                return max;
            }
        }
    }

    class Test
    {
        static void Main(string[] args)
        {
            DateTime t1 = DateTime.Now;
            int[] a = ArrayFactory.RandomIntArray(100000);
            DateTime t2 = DateTime.Now;
            //Printer<int>.PrintArray(a);
            //DateTime t3 = DateTime.Now;
            Console.WriteLine("RandomIntArray Elapsed:" + (t2 - t1).ToString());
            //Console.WriteLine("PrintArray Elapsed:" + (t3 - t2).ToString());
            MaxSubSum.MaxSubSum1(a);
            DateTime t4 = DateTime.Now;
            MaxSubSum.MaxSubSum2(a);
            DateTime t5 = DateTime.Now;
            MaxSubSum.MaxSubSum3(a);
            DateTime t6 = DateTime.Now;
            Console.WriteLine("MaxSubSum1 Elapsed:" + (t4 - t2).ToString());
            Console.WriteLine("MaxSubSum2 Elapsed:" + (t5 - t4).ToString());
            Console.WriteLine("MaxSubSum3 Elapsed:" + (t6 - t5).ToString());
            
            Console.WriteLine("-------------------------------------------");

            DateTime t11 = DateTime.Now;
            int[] b = ArrayFactory.RandomIntArray(100000, -1000, 0);
            DateTime t12 = DateTime.Now;
            Console.WriteLine("RandomIntArray Elapsed:" + (t12 - t11).ToString());
            MaxSubSum.MaxSubSum1(b);
            DateTime t13 = DateTime.Now;
            MaxSubSum.MaxSubSum2(b);
            DateTime t14 = DateTime.Now;
            MaxSubSum.MaxSubSum3(b);
            DateTime t15 = DateTime.Now;
            Console.WriteLine("MaxSubSum1 Elapsed:" + (t13 - t12).ToString());
            Console.WriteLine("MaxSubSum2 Elapsed:" + (t14 - t13).ToString());
            Console.WriteLine("MaxSubSum3 Elapsed:" + (t15 - t14).ToString());
        }
    }
}
/*output
RandomIntArray Elapsed:00:00:00.0050000
MaxSubSum1 output:185060
MaxSubSum2 output:185060
MaxSubSum3 output:185060
MaxSubSum1 Elapsed:00:00:36.5490000
MaxSubSum2 Elapsed:00:00:00.0220000
MaxSubSum3 Elapsed:00:00:00.0010000
-------------------------------------------
RandomIntArray Elapsed:00:00:00.0040000
MaxSubSum1 output:-1
MaxSubSum2 output:-1
MaxSubSum3 output:-1
MaxSubSum1 Elapsed:00:00:00.0010000
MaxSubSum2 Elapsed:00:00:00
MaxSubSum3 Elapsed:00:00:00.0010000
 */