元组的风暴之最长上升子序列
小美：还记得我们上次做的那道题目吗？求最长连续递增子序列的长度。
阿福：记得啊，当时我们用了两种方法，分别是在a[i] <=a[i-1]和a[i] > a[i-1]时更新max_len，古老师还表扬我们了呢。
小美：没错，当时你是出尽了风头啊。但是后来我又学会了一种新的方法，叫做动态规划，效率更高，代码也更简明。
阿福：真的吗？还有这么好的方法？快说给我听听。
小美：动态规划的概念很复杂，我一时半会儿也说不清楚，但我知道它是一种以空间换时间的方法，它把每个子问题的解都记录下来了，这样就能快速地求出更大规模问题的解，直到求出最优解。具体到这个题目，就是设置一个列表d，用d[i]记录元素a[i]在子序列中的位置，则最大的d[i]值就是最长子序列长度。
题目1：
求最长连续递增子序列的长度。例如，在元组(1,9,2,5,7,3,4,6,8,0)中最长连续递增子序列为(3,4,6,8)，其长度为4。
函数功能：求最长连续递增子序列的长度
函数名：def sub_num(a: tuple) -> int
参数表：a -- 元组。
返回值：返回最长连续递增子序列的长度。
示例：输入a=(1,9,2,5,7,3,4,6,8,0)，返回4
代码1：
def sub_num(a: tuple) -> int:
if not a: #a是空元组
return 0
d = [1] *len(a) # d[i]表示元素a[i]在子序列中的位置
for i in range(1, len(a)):
if a[i]> a[i-1]:
d[i] = d[i-1]+ 1
return max(d)
阿福：确实不错啊！虽然需要多设置一个列表d，但确实提高了效率，代码也更简洁了。
小美：那还用说。
古老师：士别三日，当刮目相待。小美的进步很大啊！动态规划是解决最优解问题的经典算法，相比暴力枚举和回溯算法，它的效率要高得多，应用也非常广泛。我们不妨来看一道类似的问题。
题目2：
求最长上升子序列的长度。例如，在元组(1,9,2,5,7,3,4,6,8,0)中最长上升子序列为(1,2,3,4,6,8)，其长度为6。
函数功能：求最长上升子序列的长度度
函数名：def lengthOfLIS (a: tuple) -> int
参数表：a -- 元组。
返回值：返回最长上升子序列的长度。
示例：输入a=(1,9,2,5,7,3,4,6,8,0)，返回6
小美：“最长连续递增子序列”和“最长上升子序列”有什么区别啊？
阿福：我的理解是前者必须连续，后者可以不连续。
古老师：没错，它们的区别就在于是否具有连续性，“连续子序列”又称为“子串”，要求是一个连续的序列；而“子序列”则不一定连续。
小美：哦，那判断a[i]是否属于某个上升序列的时候，就不仅仅是跟a[i-1]比较，而要与它前面的每一个元素都比较一次，加入到最长的上升序列中。我可以使用动态规划算法，只需要在代码1的基础上修改就行了。
代码2：
def lengthOfLIS(self, a: tuple) -> int:
if not a:
return 0
d = [1] *len(a) #d[i]表示以a[i]为尾元素的上升子序列长度
for i in range(1, len(a)):
for j in range(i-1, -1, -1):#逆序扫描a[i]之前的元素，更新d[i]值
if a[i]> a[j] and d[j] >= d[i]:
d[i] = d[j] + 1
return max(d)
阿福：小美是顺序扫描元组的，用d[i]记录元素a[i]在上升子序列中的位置，或者说d[i]表示以a[i]为尾元素的上升子序列长度。
我也可以逆序扫描元组，求最长下降子序列长度，用d[i]记录元素a[i]在下降子序列中的位置，或者说用d[i]表示以a[i]为首元素的上升子序列长度，这样只要在a[i]后面的元素中找到大于a[i]，且对应d[j]最大的元素a[j]就行了，我们同样更新d[i] = d[j] + 1。
代码3：
def lengthOfLIS(self, a: tuple) -> int:
if not a:
return 0
d = [1] *len(a) #d[i]表示以a[i]为首元素的上升子序列长度
for i in range(len(a)-2, -1, -1):
for j in range(i+1, len(a)):#顺序扫描a[i]之后的元素，更新d[i]值
if a[i]< a[j] and d[j] >= d[i]:
d[i] = d[j] + 1
return max(d)
古老师：都很不错！两种算法中，虽然d[i]的含义不同，但都能正确地实现程序功能，体现了动态规划算法的基本特征。但你们提供的两种算法时间复杂度都是O(n^2)，能不能将算法的时间复杂度降低到 O(n log n)呢?
我只给你们一个提示：使用对分查找算法。
好了，我该走了，再见。
彩蛋：
小美：要将算法的时间复杂度降低到 O(n log n)，那就不能写成二重循环的形式了。
阿福：是的，原来的内层循环实际上是一个顺序查找最优解的过程，现在要把顺序查找改成对分查找，这样就能实现O(n log n)的时间复杂度了。
小美：对分查找适用于有序列表，可现在列表d并不是有序列表啊。
阿福：没错。所以不能再使用列表d了，需要设置一个新的列表s，存储某些有序的元素。可哪些元素是有序的呢？
小美：我知道了，上升子序列就是有序的。列表s就用来存储最长的上升子序列。
阿福：漂亮！这就好办了。我们可以先把a[0]存储到s[0]中，之后如果a[i]> s[-1]，就把a[i]添加到列表s尾部，否则用a[i]替换s中第一个不小于a[i]的元素，使得s中的每个元素都是最小的，这样可以确保获得最长序列。
小美：什么意思啊？
阿福：没听懂是吧？我举个例子给你看看。对于元组a=(1,5,2,6,3,8,2,7,9)，我们用列表s存储最长上升子序列。我们初始化s = [a[0]]，之后遍历a[1:]，若a[i]> s[-1]，则执行s.append(a[i])，否则用a[i]替换s中第一个不小于a[i]的元素。这样可以确保s的尾元素总是最小的，让尽可能多的元素加入列表s，从而获得最长的子序列。具体操作如下图。
小美：这样我就能看懂了。那我们在列表s中查找第一个不小于a[i]的元素，是不是需要定义一个函数来实现对分查找功能呢？对分查找算法我学过，有好几种写法呢。
阿福：不用自定义函数，我记得Python提供了一个标准模块bisect，可以用实现对分查找算法。其中bisect_left(d, x)函数可以返回列表d中第一个不小于x的元素下标。
小美：还有这么好用的标准库啊，那就省事多了。代码还是我来写吧，你帮我把把关就行了。
代码4：
def lengthOfLIS(self, a: tuple) -> int:
import bisect
if not a:
return 0
s = [a[0]]#s[m]表示上升子序列中第m个元素的值
for e in a[1:]:
if e >s[-1]:#可将e加入的上升子序列尾部
s.append(e)
else: #用e替换掉s中第一个不小于e的元素，使得s中的每个元素都是最小，这样可以确保获得最长序列
s[bisect.bisect_left(s, e)] = e
return len(s)
阿福：真棒！这段代码通过“力扣”网站测试，在所有 python3 提交中击败了98.42%的用户呢。
网友评论