C# 递归查找最大值（最快）

Question

我对此没有什么想法。我自己最初尝试过，然后从 SO 和 google 复制，它适用于除一个之外的所有情况，但是仍然没有找到一种对于我的作业中的特定测试用例来说足够快的递归算法：/

无论如何，为什么会这样：

        public static int FindMaximum(int[] array)
        {
            if (array is null)
            {
                throw new ArgumentNullException(nameof(array));
            }

            if (array.Length == 0)
            {
                throw new ArgumentException(null);
            }

            return FindMaxRec(array, array.Length);
        }

        public static int FindMaxRec(int[] arr, int n)
        {
            if (n == 1)
            {
                return arr[0];
            }

            return Math.Max(arr[n - 1], FindMaxRec(arr, n - 1));
        }

不适用于此TestCase？：

        [Test]
        [Order(0)]
        [Timeout(5_000)]
        public void FindMaximum_TestForLargeArray()
        {
            int expected = this.max;
            int actual = FindMaximum(this.array);
            Assert.AreEqual(expected, actual);
        }

编辑1：

这虽然工作正常，但我需要递归：

        public static int FindMaximum(int[] array)
        {
            if (array is null)
            {
                throw new ArgumentNullException(nameof(array));
            }

            if (array.Length == 0)
            {
                throw new ArgumentException(null);
            }

            int maxValue = int.MinValue;

            for (int i = 0; i < array.Length; i++)
            {
                if (array[i] > maxValue)
                {
                    maxValue = array[i];
                }
            }

            return maxValue;
        }

Answer 1

您可以尝试将数组一分为二：

public static int FindMaximum(int[] array) {
  if (null == array)
    throw new ArgumentNullException(nameof(array));
  if (array.Length <= 0)
    throw new ArgumentException("Empty array is not allowed.", nameof(array));

  return FindMaxRec(array, 0, array.Length - 1);
}

private static int FindMaxRec(int[] array, int from, int to) {
  if (to < from)
    throw new ArgumentOutOfRangeException(nameof(to));
  if (to <= from + 1)
    return Math.Max(array[from], array[to]);

  return Math.Max(FindMaxRec(array, from, (from + to) / 2),
                  FindMaxRec(array, (from + to) / 2 + 1, to));
}

演示：

Random random = new Random(123);

int[] data = Enumerable
  .Range(0, 10_000_000)
  .Select(_ => random.Next(1_000_000_000))
  .ToArray();

Stopwatch sw = new Stopwatch();

sw.Start();

int max = FindMaximum(data);

sw.Stop(); 

Console.WriteLine($"max  = {max}");
Console.WriteLine($"time = {sw.ElapsedMilliseconds}");

结果：

max  = 999999635
time = 100