Chương trình tìm độ dài dãy con liên tiếp tăng chặt sau khi xóa tối đa một phần tử trong Python

Cho danh sách nums, tìm độ dài lớn nhất của dãy con liên tiếp tăng chặt sau khi loại bỏ tối đa một phần tử.

Ví dụ

Đầu vào: [30, 11, 12, 13, 14, 15, 18, 17, 32].
Đầu ra: 7 (xóa 18 được [11,12,13,14,15,17,32]).

Thuật toán

1. Tính mảng pre: pre[i] = độ dài dãy tăng kết thúc tại i.
2. Tính mảng suff: suff[i] = độ dài dãy tăng bắt đầu tại i.
3. Khởi tạo ans = max(max(pre), max(suff)).
4. Với i từ 1 đến n-2, nếu nums[i-1] < nums[i+1], cập nhật ans = max(ans, pre[i-1] + suff[i+1]).
5. Trả về ans.

Mã nguồn Python

class Solution:
    def solve(self, nums):
        n = len(nums)
        pre = [1] * n
        for i in range(1, n):
            if nums[i] > nums[i-1]:
                pre[i] = pre[i-1] + 1
        suff = [1] * n
        for i in range(n-2, -1, -1):
            if nums[i] < nums[i+1]:
                suff[i] = suff[i+1] + 1
        ans = max(max(pre), max(suff))
        for i in range(1, n-1):
            if nums[i-1] < nums[i+1]:
                ans = max(ans, pre[i-1] + suff[i+1])
        return ans

ob = Solution()
nums = [30, 11, 12, 13, 14, 15, 18, 17, 32]
print(ob.solve(nums))

Đầu vào / Đầu ra

Input: [30, 11, 12, 13, 14, 15, 18, 17, 32]
Output: 7