Cho danh sách số nums, tìm độ dài dãy con liên tiếp tăng chặt dài nhất. Cho phép xóa tối đa 1 phần tử.
Ví dụ
Input: nums = [35, 5, 6, 7, 8, 9, 12, 11, 26]
Output: 7
Giải thích: Xóa 12 → [5, 6, 7, 8, 9, 11, 26] độ dài 7.
Thuật toán: Mảng prefix/suffix + Ghép nối
end[i]: độ dài dãy tăng kết thúc tại i (không xóa)start[i]: độ dài dãy tăng bắt đầu tại i (không xóa)- Kết quả ban đầu = max(end), max(start) (trường hợp không xóa)
- Thử xóa từng phần tử k (1 ≤ k ≤ n-2): nếu
nums[k-1] < nums[k+1]thì ghép được:end[k-1] + start[k+1]
Mã Python
def solve(nums):
if not nums:
return 0
n = len(nums)
end = [1] * n # dãy tăng kết thúc tại i
start = [1] * n # dãy tăng bắt đầu tại i
# Tính end[]
for i in range(1, n):
if nums[i] > nums[i-1]:
end[i] = end[i-1] + 1
# Tính start[]
for j in range(n-2, -1, -1):
if nums[j+1] > nums[j]:
start[j] = start[j+1] + 1
# Kết quả không xóa
res = max(max(end), max(start))
# Thử xóa mỗi phần tử giữa
for k in range(1, n-1):
if nums[k-1] < nums[k+1]:
res = max(res, end[k-1] + start[k+1])
return res
# Test
nums = [35, 5, 6, 7, 8, 9, 12, 11, 26]
print(solve(nums)) # Output: 7Phân tích độ phức tạp
- Thời gian: O(n) - 3 vòng lặp tuyến tính
- Không gian: O(n) - 2 mảng phụ
Bài toán liên quan: LeetCode 1870 - Minimum Speed to Arrive on Time (tương tự ý tưởng xóa 1 phần tử), LeetCode 1187 - Make Array Strictly Increasing.