动态规划--最长上升子序列(LIS)的长度

发布时间：2020-12-20 09:50:38 所属栏目：Python 来源：网络整理

导读：l例如：对于[3,1,4,2,5]，最长上升子序列的长度是3 arr = [3,5,9,6,5 ,0] def lis(arr): # dp[i]表示第i个位置的值为尾的数组的最长递增子序列的长度初始化数组，假定数组中每个值的最长子序列就是它自己，即都是1 dp = [1 for _ in range(len(arr))] 遍历

l例如：对于[3,1,4,2,5]，最长上升子序列的长度是3

arr = [3,5,9,6,5,0]
def lis(arr):
    #dp[i]表示第i个位置的值为尾的数组的最长递增子序列的长度
    初始化数组，假定数组中每个值的最长子序列就是它自己，即都是1
    dp = [1 for _ in range(len(arr))]
    遍历数组
    for i  range(len(arr)):
        当遍历到第i个位置时，再依次从0开始遍历到
        for j  range(i):
            如果第i个位置的值比第j个位置的值要大，那么长度就是max(dp[j]+1,dp[i])
            if arr[i]>arr[j]:
                dp[i]=max(dp[i],dp[j]+1)
    return dp

最后输出dp：

[1,3,1]

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!