1305: 9+1-15寻找满足条件的最长子序列

[命题人 : hhg]
时间限制 : 1.000 sec  内存限制 : 128 MB

提交解决: 44提交量: 63统计

题目描述  复制

在一个正整数序列中，由若干个连续的数据元素组成的序列，称为该序列的子序列。现输入一个整数序列和一个整数 m，寻找一个满足下列条件的子序列：
①该子序列的各元素之和不能超过 m。
②在所有满足条件①的子序列中寻找长度为最大（元素个数最多）的子序列。
若满足条件的子序列有多个，则输出最左边的子序列。
例如，整数序列为“1, 5, 4, 2, 3, 1, 5, 8, 1”，m 的值为 15，则元素之和不超过 m 的最长子序列有“[1,5, 4, 2, 3]”和“[4, 2, 3, 1, 5]”，长度均为 5，根据题目要求可知，最后输出的最长子序列为“[1, 5, 4, 2,3]”。读入一个由整数组成的数据序列，输入 m，输出符合条件的最长子序列及该子序列的长度。程序运行界面如下所示。
序列为:
[1，5，4，2,3，1，5，8，1]
请输入m的值: 15
最长子序列长度为: 5
最长子序列为:[1，5，4，2，3]

输入

3,5,4,5,2,3,1,8,3,4
20

输出

5,4,5,2,3,1

样例输入  复制 

3,5,4,5,2,3,1,8,3,4
20

样例输出  复制 

最长子序列长度为： 6
最长子序列为： [5, 4, 5, 2, 3, 1]

代码填空 复制 

d=list(map(int,input().split(",")))
m=int(input())
n=len(d)
sumx=[0]*(n+1)
for i in range(1,n+1):
    __________
maxn=0
maxposi=-1
for i in range(0,n+1):
    ...
    ...
    if j-i-1>maxn:
        __________
        __________
print("最长子序列长度为：",maxn)
print("最长子序列为：",d[maxposi:maxn+maxposi])

必须/禁用关键字

无

来源/分类

2023高二9+1 
提交