Python算法之旅元组的风暴之最长连续递增序列
元组的风暴之最长连续递增序列
小美：前几天老师布置了一道题目：求最长连续递增子序列的长度。我感觉题目并不难，很快就做出来了。老师说我的代码有错误，可我没发现错误啊，我测试了好几组数据都是正确的。
阿福：有这种事情？你把代码发给我看看。
题目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
max_len, c = 1,1
for i in range(1, len(a)):
if a[i]> a[i-1]:
c += 1
else:
if c> max_len:
max_len = c
c = 1
return max_len
阿福：让我仔细瞧瞧。哦，我明白了。
小美：是吗？我的代码错在哪里了？
阿福：小美，你的程序一般情况下是能得到正确结果的，但是有一种特殊情况你没有考虑到。
小美：什么特殊情况？
阿福：如果我们把测试数据改成a=(1,9,2,5,7,3,4,6,8,10)，你认为应该返回几？
小美：最长连续递增子序列为(3,4,6,8,10)，其长度为5。应该返回5。
阿福：没错，应该返回5。你运行一下你的程序，看看返回值是多少？
小美：程序返回3。咦，怎么回事？程序出错了！让我再好好想想。。。。。。哦，我明白了，我没有考虑最后一个元素属于最长连续递增子序列的情况。需要在循环体外面再加一条判断语句，看看是否需要更新max_len的值。
代码2：
def sub_num(a: tuple) -> int:
if not a: #a是空元组
return 0
max_len, c = 1,1
for i in range(1, len(a)):
if a[i]> a[i-1]:
c += 1
else:
if c> max_len:
max_len = c
c = 1
#若最后一个元素属于最长连续递增子序列，则要在循环体外更新max_len的值
if c >max_len:
max_len = c
return max_len
阿福：没错，因为你是在a[i] <=a[i-1]时更新max_len，此时a[i]不属于当前正在处理的递增子序列，所以在循环体外还要做一次判断，若最后一个元素属于最长连续递增子序列，则要在循环体外更新max_len的值。这是正确的方法，但不是唯一的方法，我只要调整一下代码1中循环体内某些语句的位置，就可以避免出错了。
小美：是吗？不需要在循环体外更新max_len的值？
阿福：是的，如果我在a[i] > a[i-1]时更新max_len，则不需要单独判断最后一个元素。
代码3：
def sub_num(a: tuple) -> int:
if not a: #a是空元组
return 0
max_len, c = 1,1
for i in range(1, len(a)):
if a[i]> a[i-1]:
c += 1
if c> max_len:
max_len = c
else:
c = 1
return max_len
古老师：干得漂亮！阿福的代码越来越简明了。小美也不错，一点就通。“求最长连续递增子序列的长度”是一道经典的求最优解问题，使用简单的顺序查找算法就能搞定。我想在此基础上增加点难度，那就是不仅仅要求出最长连续递增子序列的长度，还要输出该子序。如果存在多个子序列长度相同，则输出第一个最长连续递增子序列。
题目2：
求首个最长连续递增子序列。例如，在元组(1,9,2,3,5,6,6,7,8,10)中首个最长连续递增子序列为(2,3,5,6)
函数功能：求首个最长连续递增子序列
函数名：def increasing_subsequence(a:tuple) -> tuple
参数表：a -- 元组。
返回值：返回存储了首个最长连续递增子序列的元组。
示例：输入a=(1,9,2,3,5,6,6,7,8,10)，返回(2,3,5,6)
小美：这个不难啊！前面的程序已经求出了最长连续递增子序列的长度，只需要再给出子序列的右边界，就能确定这个子序列了。
阿福：没错，只要在更新最长子序列长度的时候，同时更新一下右边界就行了。
古老师：很好！那你们就增加一个表示右边界的right变量，分别在代码2和代码3的基础上实现新的功能吧。
代码4：
#根据max_len和right来确定子序列
def increasing_subsequence(a: tuple) -> tuple:
if not a: #a是空元组
return ()
max_len, c, right = 1, 1, 0
for i in range(1, len(a)):
if a[i] > a[i-1]:
c += 1
else:
if c > max_len:
max_len, right = c, i - 1
c = 1
#考虑最后一个元素属于最长连续递增子序列的情形
if c > max_len:
max_len, right = c, len(a) - 1
return tuple(a[right-max_len+1:right+1])
代码5：
#根据max_len和right来确定子序列
def increasing_subsequence5(a:tuple) -> tuple:
if not a: #a是空元组
return ()
max_len, c, right = 1, 1, 0
for i in range(1, len(a)):
if a[i] > a[i-1]:
c += 1
if c > max_len:
max_len, right = c, i
else:
c = 1
return tuple(a[right-max_len+1:right+1])
古老师：都做得很好！你们都是根据max_len和right来确定子序列的，那这是唯一的方法吗？
小美：应该不是。也可以根据max_len和left来确定子序列。
阿福：还可以根据left和right来确定子序列。
古老师：完全正确！只要知道了一个子序列的左边界、右边界和长度中的任意两个条件，就可以确定这个子序列。刚才我们已经分析了其中的一种情况，接下来的另外两种情况就交给你们课后思考吧。我先走了，再见！
彩蛋：
阿福：在代码5中我可以直接用i值来更新right的值，如果是设置左边界left，又该怎么更新left的值呢？这还真有点难度呢。
小美：是啊，当a[i] > a[i-1]时，i本身就是递增子序列的右边界，直接用它更新right的值就好了，可是left的值又该取多少呢？
阿福：先让我梳理一下思路。在代码5中max_len和right分别表示最优解的长度和右边界，c和i分别表示当前解的长度和右边界。当c > max_len时，我们需要更新最优解的值。这样的话。。。。。。啊哈，我明白了！
小美：对对对，我也想到了！我们可以同时设置两个变量L和left，分别表示当前解和最优解的左边界。
阿福：没错！这样一来当前解的长度就等于i – L + 1，甚至可以省略变量c了。
小美：是的。要不这次我们换一下，你在代码4的基础上修改，我在代码5的基础上修改。
阿福：好的，各种写法都应该尝试一下。
代码6：
#根据max_len和left来确定子序列
def increasing_subsequence6(a: tuple) -> tuple:
if not a: #a是空元组
return ()
max_len, L, left = 1, 0, 0
for i in range(1, len(a)):
if a[i] <= a[i-1]:
if i - L > max_len:
max_len, left = i - L, L
L = i
#考虑最后一个元素属于最长连续递增子序列的情形
if len(a) - L > max_len:
max_len, left = len(a) - L, L
return tuple(a[left:left+max_len])
代码7：
#根据left和right来确定子序列
def increasing_subsequence7(a: tuple) -> tuple:
if not a: #a是空元组
return ()
L, left, right = 0, 0, 0
for i in range(1, len(a)):
if a[i] <= a[i-1]:
if i - L > right - left:
left, right = L, i - 1
L = i
#考虑最后一个元素属于最长连续递增子序列的情形
if len(a) - 1 - L > right - left:
left, right = L, len(a) - 1
return tuple(a[left:right+1])
代码8：
#根据max_len和left来确定子序列
def increasing_subsequence8(a: tuple) -> tuple:
if not a: #a是空元组
return ()
max_len, L, left = 1, 0, 0
for i in range(1, len(a)):
if a[i] > a[i-1]:
if i - L >= max_len:
max_len, left = i - L + 1, L
else:
L = i
return tuple(a[left:left+max_len])
代码9：
#根据left和right来确定子序列
def increasing_subsequence9(a: tuple) -> tuple:
if not a: #a是空元组
return ()
L, left, right= 0, 0, 0
for i in range(1, len(a)):
if a[i]> a[i-1]:
if i -L > right - left:
left, right = L, i
else:
L = i
return tuple(a[left:right+1])
