Chương trình tìm số dãy con chứa max và min sau khi xóa một phần tử trong Python

Cho danh sách nums, có thể xóa tối đa 1 phần tử. Tìm số dãy con (sublist - liên tiếp) chứa cả max và min của dãy kết quả, tối đa hóa số lượng này.

Ví dụ: nums = [3, 2, 6, 2, 4, 10] → 8 (xóa 10, dãy [3,2,6,2,4] có 8 dãy con chứa 2 và 6).

Giải pháp

Hàm check(lst): đếm dãy con chứa cả min và max:

• Duyệt lst, cập nhật min_pos, max_pos
• Khi cả hai đã có: ret += min(min_pos, max_pos) + 1

Thử 3 trường hợp: không xóa, xóa min (nếu chỉ có 1), xóa max (nếu chỉ có 1). Lấy max.

Ví dụ minh họa

class Solution:
    def solve(self, nums):
        if len(nums) <= 1:
            return len(nums)
        def check(lst):
            mn, mx = min(lst), max(lst)
            min_pos, max_pos = None, None
            ret = 0
            for i, num in enumerate(lst):
                if num == mn:
                    min_pos = i
                if num == mx:
                    max_pos = i
                if min_pos is None or max_pos is None:
                    continue
                ret += min(min_pos, max_pos) + 1
            return ret
        ret = check(nums)
        for rem_cand in [min(nums), max(nums)]:
            if nums.count(rem_cand) == 1:
                idx = nums.index(rem_cand)
                ret = max(ret, check(nums[:idx] + nums[idx + 1:]))
        return ret

ob = Solution()
nums = [3, 2, 6, 2, 4, 10]
print(ob.solve(nums))

Đầu vào

[3, 2, 6, 2, 4, 10]

Đầu ra

8