为什么我的递归最长递增子序列函数不适用于大输入？

Question

我写它是为了一次处理一个测试用例。 在线评委花费的时间太长或返回错误的答案

来源：我用来测试它的问题

它非常适合小箱子：

#include <iostream>
  #include <algorithm>
  #include <vector>
  int LIS[100000];
  void LS (int *arr , int n)
  {
      if (n == 0)
      {
          LIS[0] = 1;
          return;
      }
      if (LIS[n])
      {
          return;
      }
      int i = 0;
      int max = 0;
      while (i < n)
      {
          if (arr[i] < arr[n])
          {
              LS(arr,i);
              if (LIS[i] + 1 > max)
              {
                  max = 1 + LIS[i];
              }
          }
          ++i;
      }
      LIS[n] = max;
  }
  int main()
  {
      int n;
      std::cin >> n;
      int arr[n];
      for(int i = 0 ; i < n ; ++i) std::cin >> arr[i];
      LS(arr,n-1);
      std::sort (LIS , LIS+n);
      std::cout << "n" << LIS[n-1] << "n";
  }

Answer 1

你说它适用于完美的小情况......而不是可能是堆栈溢出..

函数调用消耗堆栈内存。

如果递归调用深度太深，堆栈内存耗尽并崩溃。

Answer 2

当你从std::cin读取int n值时，你必须为数组arr动态分配内存，所以你应该首先声明int *arr，然后以与现在相同的方式获取用户输入，然后使用arr = new int[n]分配内存。

当谈到使用递归函数计算下一个值所需的时间时，您应该考虑将函数重新制作为使用尾递归，这更接近迭代。您可以通过编写两个程序来计算斐波那契数 - 一个递归和另一个迭代，然后检查使用这两种方法计算~50个值需要多长时间。