Longest Increasing Subsequence (LIS) means a sequence containing someelements in another sequence by the same order, and the values ofelements 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 Nelements, what is the average time and space complexity to get thelength 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