在Python中找到删除后连续严格递增子列表的最大长度
假设我们有一个名为nums的数字列表,我们必须找到连续严格递增子列表的最大长度。我们允许从列表中最多删除单个元素。
因此,如果输入是nums = [35、5、6、7、8、9、12、11、26],则输出将为7,因为如果我们从nums中删除12,列表将为[5、6、7、8、9、11、26],长度为7,这是最长的、连续的、严格递增的子列表。
为了解决这个问题,我们将按照以下步骤进行——
- 如果nums为空,则
- 返回0
- 结束:与nums相同大小的列表,并填充为1
- 开始:与nums相同大小的列表,并填充为1
- 对于范围为1到nums大小-1的i,执行以下操作
- 如果nums [i]> nums [i-1],则
- end [i]:= end [i-1]+1
- 如果nums [i]> nums [i-1],则
- 对于范围为nums大小-2到0的j,递减1,执行以下操作
- 如果nums [j + 1]> nums [j],则
- start [j]:= start [j + 1] + 1
- 如果nums [j + 1]> nums [j],则
- res:最大的end元素和start元素之一
- 对于范围为1到nums大小-2的k,执行以下操作
- 如果nums [k-1]
- res:= res和(end [k-1] + start [k + 1])中的最大值
-
返回res
示例
让我们看以下实现以更好地理解——
def solve(nums):
if not nums:
return 0
end = [1 for i in nums]
start = [1 for i in nums]
for i in range(1, len(nums)):
if nums[i]> nums[i-1]:
end[i]= end[i-1]+ 1
for j in range(len(nums)-2, -1, -1):
if nums[j+1]> nums[j]:
start[j]= start[j+1]+ 1
res= max(max(end), max(start))
for k in range(1, len(nums)-1):
if nums[k-1]< nums[k+1]:
res= max(res, end[k-1]+ start[k+1])
return res
nums= [35, 5, 6, 7, 8, 9, 12, 11, 26]
print(solve(nums))
输入
[35, 5, 6, 7, 8, 9, 12, 11, 26]
输出
7