最长上升子序列是一种经典的计算机算法问题，即对于一个序列，找出其中的一个子序列，使得它的元素按照顺序递增，并且它的长度最大。最长上升子序列问题在多个领域都有应用，比如文本相似度匹配、基因序列匹配、信号处理等等。
一、基本思路
最长上升子序列问题的基本思路是使用动态规划，通过保存之前的计算结果，不断递推得到当前的最长上升子序列。具体地说，我们定义一个dp数组，其中dp[i]表示以第i个位置为结尾的最长上升子序列的长度。然后，我们可以通过枚举之前的位置j，如果当前位置i的值大于位置j的值，并且dp[i]< dp[j]+1，那么我们就可以更新dp[i]的值。
// 最长上升子序列动态规划代码示例 int lengthOfLIS(vector& nums) { int n = nums.size(), ans = 0; vector dp(n, 1); for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) { if (nums[j] < nums[i]) { dp[i] = max(dp[i], dp[j] + 1); } } ans = max(ans, dp[i]); } return ans; }
在代码中，我们定义了一个n长度的dp数组，初始值都为1，然后通过两层循环，不断更新dp数组的值。最后，在所有的dp数组中找到最大值就是我们需要的最长上升子序列的长度。
二、优化思路
在最长上升子序列问题中，可不需要完全使用动态规划的方法来求解，还有更加巧妙高效的解法。比如，我们可以使用二分查找，对于每个元素，二分查找可以确定它可以插入到最长上升子序列中的哪个位置。
具体来说，我们维护一个tails数组，tails[i]表示最长上升子序列长度为i+1的序列尾部元素的最小值。对于每个新来的数num，如果num大于tails数组中的最大值，那么就可以直接将其插入到tails数组的最后，相当于我们扩展了当前的最长上升子序列；否则，我们使用二分查找在tails数组中找到第一个大于等于num的元素的位置，并更新tails数组。这个过程可以保证tails数组中不同位置的元素之间是递增的。
// 最长上升子序列二分查找代码示例 int lengthOfLIS(vector& nums) { int n = nums.size(), len = 0; vector tails(n, 0); for (int i = 0; i < n; ++i) { int l = 0, r = len; while (l < r) { int mid = (l + r) >> 1; if (tails[mid] < nums[i]) l = mid + 1; else r = mid; } tails[l] = nums[i]; if (l == len) len++; } return len; }
相较于动态规划的方法，使用二分查找可以将时间复杂度从O(n^2)降低到O(nlogn)。在实际应用中，我们应根据实际情况选择合适的算法。
三、总结
最长上升子序列问题是经典的计算机算法问题，使用动态规划和二分查找方法均可解决。动态规划是基于之前的计算结果，进行逐步递推，时间复杂度为O(n^2)；二分查找则与tails数组中元素位置有关，可以将时间复杂度优化至O(nlogn)。在实际应用中，应根据实际情况选择合适的算法，这也是算法优化的一个方向。