(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()); } }}/*outputRandomIntArray Elapsed:00:00:00.0050000MaxSubSum1 output:185060MaxSubSum2 output:185060MaxSubSum3 output:185060MaxSubSum1 Elapsed:00:00:36.5490000MaxSubSum2 Elapsed:00:00:00.0220000MaxSubSum3 Elapsed:00:00:00.0010000-------------------------------------------RandomIntArray Elapsed:00:00:00.0040000MaxSubSum1 output:-1MaxSubSum2 output:-1MaxSubSum3 output:-1MaxSubSum1 Elapsed:00:00:00.0010000MaxSubSum2 Elapsed:00:00:00MaxSubSum3 Elapsed:00:00:00.0010000 */