def basic_lis(seq): l=[1]*len(seq) for cur ,val in enumerate(seq): #enumerate返回元素的"索引和值" for pre in range(cur): if seq[pre]<val: l[cur]=max(l[cur],1+l[pre]) return max(l) L=[49, 64, 17, 100, 86, 66, 78, 68, 87, 96, 19, 99, 35] print(basic_lis(L)) 解释并且告诉我运算过程
时间: 2024-04-02 14:37:40 浏览: 19
这段代码是用来求一个序列的最长递增子序列的长度(LIS问题)。下面是运算过程的说明:
首先,定义了一个列表 l,它的长度与原序列的长度相同,初始化所有元素为 1。
接着,使用两层循环遍历序列。外层循环使用 enumerate 函数同时获取当前元素的索引和值,内层循环则遍历当前元素之前的所有元素。如果前面的元素比当前元素小,说明可以将当前元素加入到前面的递增子序列中,从而得到一个更长的递增子序列。此时,更新 l[cur] 的值,即取 l[cur] 和 l[pre]+1 中的较大值。
最后,返回 l 中的最大值,即为原序列的最长递增子序列的长度。
以 L=[49, 64, 17, 100, 86, 66, 78, 68, 87, 96, 19, 99, 35] 为例,运算过程如下:
1. 初始化 l=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
2. 对于元素 49,l[0]=1。
3. 对于元素 64,l[1]=max(l[1], l[0]+1)=2。
4. 对于元素 17,l[2]=max(l[2], l[0]+1)=2。
5. 对于元素 100,l[3]=max(l[3], l[0]+1, l[1]+1, l[2]+1)=3。
6. 对于元素 86,l[4]=max(l[4], l[0]+1, l[1]+1, l[2]+1)=3。
7. 对于元素 66,l[5]=max(l[5], l[0]+1, l[1]+1, l[2]+1, l[4]+1)=4。
8. 对于元素 78,l[6]=max(l[6], l[0]+1, l[1]+1, l[2]+1, l[4]+1)=4。
9. 对于元素 68,l[7]=max(l[7], l[0]+1, l[1]+1, l[2]+1, l[4]+1, l[5]+1)=5。
10. 对于元素 87,l[8]=max(l[8], l[0]+1, l[1]+1, l[2]+1, l[4]+1, l[5]+1, l[6]+1)=5。
11. 对于元素 96,l[9]=max(l[9], l[0]+1, l[1]+1, l[2]+1, l[4]+1, l[5]+1, l[6]+1, l[8]+1)=6。
12. 对于元素 19,l[10]=max(l[10], l[2]+1)=3。
13. 对于元素 99,l[11]=max(l[11], l[0]+1, l[1]+1, l[2]+1, l[4]+1, l[5]+1, l[6]+1, l[8]+1)=7。
14. 对于元素 35,l[12]=max(l[12], l[2]+1)=4。
15. 返回 l 中的最大值 7,即为序列的最长递增子序列的长度。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![gz](https://img-home.csdnimg.cn/images/20210720083447.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)