本文最后更新于255 天前，其中的信息可能已经过时，如有错误请发送邮件到1986413837@qq.com
方法一 : 动态规划 O(n^2)
定义 dp[i] 为考虑前 i 个元素，以第 i 个数字结尾的最长上升子序列的长度
状态转移方程为：
dp[i]=max(dp[j])+1,其中0≤j<i且num[j]<num[i]
最终 LISlength=max(dp[i]),其中0≤i<n
补充 : 如果想使用动态规划返回LIS数组 而不是数组长度 就应该记录每个元素在LIS中的前驱节点索引 然后从最长序列的末尾开始，通过prev指针反向追踪，重建整个序列
方法二 贪心 + 二分查找 O(nlogn)
LIS算法和Vue3中 Diff算法的关系
Vue 3 的 Diff 算法利用「最长递增子序列」来最大化地复用 DOM 元素，从而减少移动操作的次数 这主要应用于处理 v-for 渲染的列表更新场景
Vue 3 在对比列表节点时，利用 LIS(Longest Increasing Subsequence) 算法来最小化 DOM 的移动操作
通过标记出不需要移动的节点，只对剩下的节点进行移动，极大地提升了 v-for 列表更新的性能