[LeetCode]Longest Increasing Subsequence.cpp

如果用DP[i]表示以nums[i]结尾的LIS(Longest Increasing Subsequence)的长度，那么我们可以得到递推公式：

• DP[i] = max(DP[k]) + 1 (0 <= k < i &&  nums[i] > nums[k])

那么根据这个我们可以写出代码，时间复杂度O(n^2)，空间复杂度O(n):

我们在Increasing Triplet Subsequence也提到过如何判断长度为k的IS(Increasing Subsequence)是否存在的方法。其更新DP的时候，由于DP本身就是sorted的，可以用binary search完成，这样时间复杂度可以到O(n * log n)，空间为O(len)，len为LIS的长度，代码如下;