Longest Increasing Subsequence-DP Approach to Subsequence
在解决二最长递增子序列问题时，我们使用动态规划（DP）方法来实现。设L为一个包含n个不同实数的序列，目标是找到L的最长递增子序列（LIS）。一个递增子序列是一个从L中选出的子集，且这个子集是按递增顺序排列的。
动态规划的基本思路是，通过维护一个数组来存储每个位置之前的最长递增子序列的长度，逐步更新这个值。对于每一个元素，判断它能接在之前哪些元素的后面，从而更新它的LIS长度。
这一过程的时间复杂度通常为O(n^2)，但是可以通过二分查找优化到O(n log n)。
文件大小：529KB
评论区