LIS :最长递增子序列问题是找到给定序列的子序列，其中子序列的元素按从低到高的顺序排列
例如:
0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
A longest increasing subsequence is 0, 2, 6, 9, 13, 15.
我可以使用动态规划和内存技术等不同方式开发 LIS，但在特定情况下，我喜欢使用时间复杂度为 O(N^2) 的递归来实现 LIS .
我认为使用递归我们无法实现具有时间复杂度的算法 O(N^2) .(请指正)
但是我从谷歌得到这个算法
Algorithm LIS(A,n,x)
1: if n = 0 then
2: return 0
3: m LIS(A; n -1; x)
4: if A[n] < x then
5: m =max(m; 1 + LIS(A; n-1;A[n]))
6: print(m)
这个算法是O(N^2) ？
你能解释一下吗？
最佳答案
此算法打印数组中的最大值 第一个参数 (A) 是数组，第二个参数 (n) 是现在检查最大值的项的索引，第三个参数 (x) 是当时的最大值。 在最坏的情况下，你有一个排序的数组，并且在每次检查中(如果 A[n] < x 那么)你必须用 max 更新第三个参数，这意味着你最多必须检查所有数组。
该算法从索引 n 到 n-1 取一个最大值，并检查从 n 到 n-2 的最大值，并检查 n 到 n-3 索引中的最大值，然后继续检查 n 到 1 以获得最大值项目。
这意味着它是 O(n+(n-1)+(n-2)+...+2+1) = O(n^2)
抱歉图片质量:)
关于java - 使用递归的 O(n^2) 的最大递增子序列，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26770846/