关于#c语言#的问题：LCS（最长公共子序列）能否都能通过LIS（最长递增子序列）把时间复杂度降到O（nlogn）

Question

LCS（最长公共子序列）能否都能通过LIS（最长递增子序列）把时间复杂度降到O（nlogn）

Answer 1

该回答引用GPT，有帮助的话请帮我点个采纳

LCS通常使用动态规划法进行计算，其时间复杂度为O(mn)，其中m和n分别是两个序列的长度。

而LIS可以使用O(nlogn)的算法，如二分查找法或者动态规划法。

所以，LCS不一定通过LIS的方法来降低其时间复杂度到O（nlogn）。