300. Longest Increasing Subsequence

Descrtiption:

Solution:

We are gonna start from the last value of array.

ex)

nums = [1 ,2 ,4, 3]

LIS[3] = 1

LIS[2] = max(1, 1 + LIS[3]) = 1  (nums[2] > nums[3])

LIS[1] = max(1, 1 + LIS[2], 1 + LIS[3]) = 2

LIS[0] = max(1, 1+1, 1+1, 1+2) = 3 

 

So, the answer is 3.

 

Time Complexity: O(n^2)