Максимум в неупорядоченном массиве через рекурсию

Question

Использовать Linq запрещено. Мой код не работает, когда массив огромный (10_000_000 ).

выпадает вот такая ошибка Stack overflow. Repeat 16069 times

когда массив больше 10_000

есть мысли, что нужно делить исходный массив на части, и обрабатывать уже эти части. Но вообще нет идеи, как это через рекурсию реализовать. Циклы использовать нельзя.

class Program
{
    public static int FindMaximum(int[] array)
    {
        if (array is null)
        {
            throw new ArgumentNullException($"{array} is null");
        }

        if (array.Length == 0)
        {
            throw new ArgumentException($"{array} is empty");
        }

        int result = array[0];

        int lastNumber = array.Length - 1;

        return FindMaximumOne(array, result, 0, lastNumber);
    }

    public static int FindMaximumOne(int[] array, int result, int i, int lastNumber)
    {
        if (i >= lastNumber)
        {
            return result;
        }

        if (array[i] > result)
        {
            result = array[i];
        }

        if(array[lastNumber] > result)
        {
            result = array[lastNumber];
        }

        i++;
        lastNumber--;

        return FindMaximumOne(array, result, i, lastNumber);
    }
    static void Main(string[] args)
    {
        int[] array = new int[] { -50, -25, -20, -5, -500, -100 };

        Console.WriteLine(FindMaximum(array));
    }
}

Answer 1

Вы за один рекурсивный вызов отсекаете 2 элемента массива, потому на больших массивах у вас переполняется стек. Отсекайте на каждой итерации хотя бы половину, тогда глубина стека вам не будет помехой, пример

public static int FindMax(int[] array)
{
    return FindMax(array, 0, array.Length - 1);
}

public static int FindMax(int[] array, int start, int end)
{   
    if (end - start <= 1) return Math.Max(array[start], array[end]);    
    var mid = start + (end - start)/2;  
    return Math.Max(FindMax(array, start, mid), FindMax(array, mid, end));
}

БЛОГ НА HUSL

Максимум в неупорядоченном массиве через рекурсию

Ответы (1 шт):