I'm out of ideas on this one. Tried originally myself and then copied from SO and google, which worked on all cases except one, however still didn't find a recursive algorithm that is fast enough for that particular test case in my assignment :/

In any case, why this:

        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));
        }

doesn't work with this TestCase?:

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

EDIT 1:

This works fine though, but I need recursive:

        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;
        }

CodePudding user response：

You can try splitting array in 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));
}

Demo:

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}");

Outcome:

max  = 999999635
time = 100

CodePudding user response：

An easy way to turn a simple linear algorithm into a recursive one is to make use of the enumerator of the array.

    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);
    }

This passes your test case and uses recursion.

Edit: Here is a more beginner friendly version of the above, with comments to explain what it is doing:

    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
    }

Something that might help understand this is that the IEnumerator is what enables foreach loops. Under the hood, foreach loops are just repeatedly calling MoveNext on an item that has an IEnumerator. Here is some more info on that topic.

CodePudding user response：

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