单选题

最长递增子序列（LIS）问题是指，在一个给定的数值序列中，找到一个子序列，...

Question

最长递增子序列（LIS）问题是指，在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。

比如{2,1,4,2,3,7,4,7,19} 的LIS是 {1,2,3,4,7,19}，长度是6。

考虑大小为N的数组，获取其LIS的最小时间和空间复杂度分别为：

A. N^2，N^2

B. NlogN，N^2

C. NlogN，NlogN

D. NlogN，N