首页 > 9-13度小满笔试,第二题
头像
大菊已定
编辑于 2020-09-13 21:45
+ 关注

9-13度小满笔试,第二题

一共有多少个最长上升子序列

本地测试没任何问题,大概思路是:获取原序列的动态规划表,找到表中最大值m,也就是最长的子序列长度,然后收集小于等于m的数字,做一个排列就可以了。代码如下:

def test02():
    n = int(input().strip())
    arr = list(map(int, input().strip().split(" ")))
    dp = getDp(arr)
    lenArr = len(arr)
    numC = {}
    maxV = max(dp)
    maxIndex = 0
    for i in range(lenArr - 1, -1, -1):
        if dp[i] == maxV:
            maxIndex = i
            break
    for i in range(maxIndex + 1):
        numC[dp[i]] = numC.get(dp[i], 0) + 1
    res = 1
    for k, v in numC.items():
        res *= v
    # print(numC)
    print(res % 1000000007)
# 9
# 2 1 5 3 6 4 8 9 9 10

def getDp(arr):
    lenArr = len(arr)
    dp = [1 for _ in range(lenArr)]
    for i in range(lenArr):
        dp[i] = 1
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    # print(dp)
    return dp


if __name__ == '__main__':
    # arr = [1, 3, 6, 4, 7]
    # getDp(arr)
    test02()

就过了18%,哪些情况没考虑到呢 求指出。

全部评论

(0) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐