最长上升子序列（LIS）是一个经典的算法问题，它要求在给定的数列中找到一个最长的子序列，使得这个子序列中的元素是严格递增的。例如13，7，9，16，38，24，37，18，44，19，21，22，63，15。例中13，16，18，19，21，22，63就是一个长度为7的上升子序列，同时也有7 ，9，16，18，19，21，22，63长度为8的上升子序列。在相同长度的情况下，选择第一个出现的子序列，如1，4，5，3，6，8，7，9，则输出1，4，5，6，8，9。
使用动态规划的方法是，对于每个元素，记录以该元素结尾的最长递增子序列的长度。具体来说，定义 dp[i] 为前i个元素中，以第i个元素结尾的最长递增子序列的长度。然后，对于每个元素，遍历之前的所有元素，如果前面的元素小于当前元素，且以前面元素结尾的最长递增子序列的长度不小于以当前元素结尾的最长递增子序列的长度，则更新 dp[i] 的值。最终，dp 的最大值就是 LIS 的长度。