Longest Contiguously Strictly Increasing Sublist After Deletion

# 题目描述

1
Given a list of integers nums, return the maximum length of a contiguous strictly increasing sublist if you can remove one or zero elements from the list.
2
3
Constraints
4
5
n ≤ 100,000 where n is the length of nums
6
Example 1
7
Input
8
nums = [30, 1, 2, 3, 4, 5, 8, 7, 22]
9
Output
10
7
11
Explanation
12
If you remove 8 in the list you can get [1, 2, 3, 4, 5, 7, 22] which is the longest, contiguous, strictly increasing list.
Copied!

• 动态规划

# 思路

• dp[i] 表示以 nums[i] 结尾的删除 0 个数的情况下的最长严格递增子数组。
• dp[i] 表示以 nums[i] 结尾的删除 1 个数的情况下的最长严格递增子数组。

• 如果 nums[i] > nums[i-1]，那么 dp[i] 和 dp[i] 都可以在前一个的基础上 + 1。也就是：
1
dp[i] = dp[i-1] + 1
2
dp[i] = dp[i-1] + 1
Copied!
• 否则 dp[i] = dp[i] = 1

• 首先状态中列的长度要变成 k
• 其次，我们往前比较的时候要比较 nums[i-1], nums[i-2], ... , nums[i-k-1]，取这 k + 1 种情况的最大值。

• 连续性 DP

# 代码

Python3 Code:
1
class Solution:
2
def solve(self, nums):
3
n = len(nums)
4
if not n: return 0
5
dp = [[1, 0] for _ in range(n)]
6
ans = 1
7
8
for i in range(1,n):
9
if nums[i] > nums[i-1]:
10
dp[i] = dp[i-1] + 1
11
dp[i] = dp[i-1] + 1
12
else:
13
dp[i] = 1
14
dp[i] = 1
15
if i > 1 and nums[i] > nums[i-2]:
16
dp[i] = max(dp[i], 1 + dp[i-2])
17
ans = max(ans, dp[i], dp[i])
18
19
return ans
Copied!

• 时间复杂度：\$O(n)\$
• 空间复杂度：\$O(n)\$