C#递归查找数组最大值算法大数组测试用例超时问题求解

问题根因 #

你当前的递归代码属于线性递归，递归深度和输入数组的长度完全相等：

• C# 默认线程栈大小仅为1MB，当测试用例的数组长度超过1~2万时，过深的递归调用会直接触发栈溢出异常；就算数组长度没到栈溢出阈值，逐层递归调用的额外开销也远高于迭代版本，很容易触发测试用例的5秒超时限制。

优化递归方案 #

改用二分法分治递归实现，递归深度仅为 log2(数组长度)，哪怕是千万级长度的数组，递归深度也只有20多层，完全不会出现栈溢出问题，性能接近迭代版本，可以轻松通过大数组测试：

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

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

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

// 分治递归：left为子数组起始下标，right为子数组结束下标
private static int FindMaxRecDivide(int[] arr, int left, int right)
{
    // 子数组仅含一个元素时直接返回
    if (left == right)
    {
        return arr[left];
    }

    // 拆分左右子数组
    int mid = left + (right - left) / 2;
    int leftMax = FindMaxRecDivide(arr, left, mid);
    int rightMax = FindMaxRecDivide(arr, mid + 1, right);
    
    return Math.Max(leftMax, rightMax);
}

内容的提问来源于stack exchange，提问作者Linascts