单选题

Longest Increasing Subsequence (LIS) means a sequence containing some elements in another sequence by the same order, and the values of elements keeps increasing.Considering an array with N elements, what is the lowest time and space complexity to get the

Question

Longest Increasing Subsequence (LIS) means a sequence containing some elements in another sequence by the same order, and the values of elements keeps increasing.For example, LIS of {2, 1, 4, 2, 3, 7, 4, 6} is {1, 2, 3, 4, 6}, and its LIS length is 5. Considering an array with N elements, what is the average time and space complexity to get the length of LIS?

A. Time: N^2, Space: N^2

B. Time: N^2, Space: N

C. Time: NlogN, Space: N

D. Time: N, Space: N

E. Time: N, Space: C