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

Question

我编写它是为了一次处理一个测试用例。要么在线评判时间过长，要么返回错误答案

来源:problem我曾经测试过

它非常适合小案例:

#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

你说它在小情况下工作得很好..而不是堆栈溢出..

函数调用消耗堆栈内存..

如果递归调用深度太深，堆栈内存用完，崩溃..