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

您可以尝试将数组拆分为two：

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

Answer 2

将简单线性算法转变为递归算法的一种简单方法是利用数组的

enumerator

。

    public static int FindMax(int[] values)
    {
        using var enumerator = values.GetEnumerator();
        return FindMaxRecursively(enumerator, int.MinValue);
    } 

    private static T FindMaxRecursively<T>(IEnumerator<T> enumerator, T currentMax) where T : IComparable
    {
        if (!enumerator.MoveNext()) return currentMax;
        var currentValue = enumerator.Current;
        if (currentValue.CompareTo(currentMax) > 0) currentMax = currentValue;
        return FindMaxRecursively(enumerator, currentMax);
    }

这通过了您的测试用例并使用递归。

编辑：这是上述内容的更适合初学者的版本，并带有注释来解释它在做什么：

    public static int FindMax(IEnumerable<int> values)
    {
        using var enumerator = values.GetEnumerator();//the using statement disposes the enumerator when we are done
        //disposing the enumerator is important because we want to reset the index back to zero for the next time someone enumerates the array
        return FindMaxRecursively(enumerator, int.MinValue);
    } 


    private static int FindMaxRecursively(IEnumerator<int> enumerator, int currentMax)
    {
        if (!enumerator.MoveNext()) //move to the next item in the array. If there are no more items in the array MoveNext() returns false
            return currentMax; //if there are no more items in the array return the current maximum value
        var currentValue = enumerator.Current;//this is the value in the array at the current index
        if (currentValue > currentMax) currentMax = currentValue;//if it's larger than the current maximum update the maximum
        return FindMaxRecursively(enumerator, currentMax);//continue on to the next value, making sure to pass the current maximum
    }

可能有助于理解这一点的是，

IEnumerator

是启用

foreach

循环的原因。在幕后，

foreach

循环只是在具有

MoveNext

的项目上重复调用

IEnumerator

。 这里是有关该主题的更多信息。

Answer 3

public static int findMax(int[] a, int index) {
    if (index > 0) {
        return Math.max(a[index], findMax(a, index-1))
    } else {
        return a[0];
    }
}

Answer 4

class Program1
{
public static void Main(String[] args)
{
int[] arr = { 1, 2, 3, 4, 59, 8, 9 };         
Program1 prog = new Program1();
int max = prog.maximum(arr, 0, 0);
Console.WriteLine(max);
}
int maximum(int[] arr, int max, int i)
{
 if (i == arr.Length)
 return max;
 if (max < arr[i])
 return   maximum(arr, arr[i], ++i);
 else
 return maximum(arr, max, ++i);
 }
 }