问题描述
编写一个函数，该函数接受一个整数列表作为参数，计算这个列表的最长递增子序列(LIS)的长度，这个也是动态规划中常见的问题。
举一个典型的场景：
用来查找股票价格的最大增长，比如股票价格是[12, 13, 11, 14, 15, 16, 10, 9, 8, 7]， 股票价格的最大增长是[12, 13, 14, 15, 16]，最大增长的长度是5。
通过查找出股票价格的最大增长，可以将这部分数据进行标注，找出股票价格的连续增长的趋势。
测试代码
int[] arr = { 10, 22, 9, 33, 21, 50, 41, 60, 80 };
assertEqual(lis(arr), 6, "1");
int[] arr1 = { 12, 13, 11, 14, 15, 16, 10, 9, 8, 7 };
assertEqual(lis(arr1), 5, "2");
int[] arr2 = { 10, 9, 2, 3, 4, 1 };
assertEqual(lis(arr2), 3, "3");
解决思路
在最长递增子序列（Longest Increasing Subsequence，简称 LIS）的定义中，子序列的元素不需要在原数组中连续。它们可以在原数组中的任何位置，只要它们的相对顺序保持不变。
对于数组 {10, 22, 9, 33, 21, 50, 41, 60, 80}，其最长递增子序列为 {10, 22, 33, 50, 60, 80}。这个子序列并不包括 41，因为 41 小于它前面的元素50。
在这个子序列中，每个元素都大于它前面的元素，所以它是递增的。并且这个子序列的长度（6）是所有递增子序列中最长的，所以它是最长递增子序列。
在计算最长递增子序列时，我们并不是简单地从数组的开始到结束检查每个元素。相反，我们使用一个动态规划的方法，对于每个元素，我们都检查它前面的所有元素，看看是否可以通过添加当前元素来延长一个已经存在的递增子序列。
这就是为什么 41 没有被包括在最长递增子序列中的原因，因为它不能延长任何已经存在的递增子序列。