一道有趣的最长子序列问题
一道有趣的最长子序列问题 – 潘登同学的金融经济学笔记
文章目录
- 一道有趣的最长子序列问题 -- 潘登同学的金融经济学笔记
- 来源
- 求解
- 递推公式
- 算法实现
来源
前几天在刷视频的时候，发现了这样一道题
所谓子序列就是一个序列 ai1,ai2,⋯,aina_{i1},a_{i2},\cdots,a_{in}ai1,ai2,⋯,ain满足i1 一个具体例子： 数学证明的方法，显然我是不太会，还请各位大神赐教； 但是基于置信度的解法，我还是会一点滴； 用一个记号(x,y)(x,y)(x,y)表示，从某个数开始，x表示从该数开头的最长递增序列，y表示从该数开始最长的递减序列； 从长度为2的序列说起 到长度为3的序列 到长度为4的序列(相当于在长度为3的序列前加一个数) 倒数第三个数记号为(3,1)(3,1)(3,1) 倒数第三个数记号为(2,2)(2,2)(2,2)，因为(2,2)(2,2)(2,2)有两种情况 若倒数第四个数比倒数第三个数小且比倒数第二个数小，记为(3,2)(3,2)(3,2) 若倒数第四个数比倒数第三个数小且比倒数第二个数大，记为(2,2)(2,2)(2,2) 若倒数第四个数比倒数第三个数大，记为(2,3)(2,3)(2,3) 倒数第三个数记号为(1,3)(1,3)(1,3) 当然了，这样的递推能无限进行下去，但是我们还是想从中找到规律，当序列比较短(2,3左右)的时候，我们似乎只需要比较这个数与后一个数的大小关系，一旦序列变长了之后，我们不仅需要比较这个数与下一个数的大小关系，还需要比较这个数与后两个数的大小关系，而且还是有时候需要比较而有时又无需比较，我们需要总结一个递推式；我们将目光放到我们的记号(x,y)(x,y)(x,y)上； 那么很自然地，我们就去对这个数与其后的数进行比大小，就能确定该数的记号；那么对每个数都与后面的数比一次，粗略来看算法复杂度就是O(n2)O(n^2)O(n2) 算法非常简单啊， 非常长的序列我们很难验证，但是验证长度为4的序列就足够了，下面是几次运行的结果,能看出与我们的分析是一致的 接着我们来计算序列为300长度的最长子序列 显然经过1000次的模拟，得到的最短的最长子序列也是27，所以有99.99%的把握认为能找到一个长度为17的单调子序列；求解
递推公式
∀ai,∃ai+k,若ai算法实现
import random
num = 4
a = [random.randint(0,400) for _ in range(num)]
print('数据len:',len(a))
print(a)dp_x = [1 for _ in range(num)] # 记号(x,y)
dp_y = [1 for _ in range(num)] # 记号(x,y)
for i in range(num):index = num-1 - i # 表示现在这个数的索引for j in range(index+1,num):# 表示找到了目前为止最大的xif a[index] <= a[j] and dp_x[index] <= dp_x[j]:dp_x[index] = dp_x[j] + 1# 表示找到了目前为止最大的yif a[index] >= a[j] and dp_y[index] <= dp_y[j]:dp_y[index] = dp_y[j] + 1print('最长递增子序列的长度为:',max(dp_x))
print('最长递减子序列的长度为:',max(dp_y))
import random
for _ in range(1000):result = []num = 300a = [random.randint(0,1000) for _ in range(num)]# print('数据len:',len(a))# print(a)dp_x = [1 for _ in range(num)] # 记号(x,y)dp_y = [1 for _ in range(num)] # 记号(x,y)for i in range(num):index = num-1 - i # 表示现在这个数的索引for j in range(index+1,num):# 表示找到了目前为止最大的xif a[index] <= a[j] and dp_x[index] <= dp_x[j]:dp_x[index] = dp_x[j] + 1# 表示找到了目前为止最大的yif a[index] >= a[j] and dp_y[index] <= dp_y[j]:dp_y[index] = dp_y[j] + 1# print('最长递增子序列的长度为:',max(dp_x))# print('最长递减子序列的长度为:',max(dp_y))result.append(max(dp_x))result.append(max(dp_y))
print('1000次循环中,300长度的序列中最短的最长子序列的长度为:',min(result))
