单选题

一个数组求其最长递增子序列(LIS),例如数组{3, 1, 4, 2, 3...

Question

一个数组求其最长递增子序列(LIS),例如数组{3, 1, 4, 2, 3, 9, 4, 6}的LIS是{1, 2, 3, 4, 6}，长度为5，假设数组长度为N，求数组的LIS的长度,那么最好的解法情况下,时间复杂度和空间复杂度都是多少?

A. 时间: O(N^2), 空间:O(N)

B. 时间: O(NlogN), 空间:O(N)

C. 时间: O(N), 空间:O(N)

D. 时间: O(N), 空间:O(NlogN)

E. 时间: O(NlogN), 空间:O(NlogN)