Chương trình tìm độ dài danh sách con tăng rồi giảm dài nhất trong Python

Mô tả bài toán

Cho danh sách nums. Tìm độ dài danh sách con liên tiếp (độ dài ≥ 3) mà các giá trị tăng chặt rồi giảm chặt.

Ví dụ: nums = [8, 2, 4, 6, 3, 1] → đầu ra 5 (danh sách con [2,4,6,3,1]).

Giải thuật (Duyệt một lần)

1. Khởi tạo i = 0, n = len(nums), res = -inf.
2. Khi i < n - 2:
   • st = i, linc = 0, ldec = 0.
   • Tăng i và linc khi nums[i] < nums[i+1].
   • Tăng i và ldec khi nums[i] > nums[i+1].
   • Nếu linc > 0 và ldec > 0: res = max(res, i - st + 1).
   • Bỏ qua các phần tử bằng nhau: tăng i khi nums[i] == nums[i+1].
3. Trả về res nếu ≥ 0, ngược lại 0.

Ví dụ mã Python

class Solution:
    def solve(self, a):
        i, n, res = 0, len(a), float("-inf")
        while i < n - 2:
            st = i
            linc, ldec = 0, 0
            while i < n - 1 and a[i] < a[i + 1]:
                linc += 1
                i += 1
            while i < n - 1 and a[i] > a[i + 1]:
                ldec += 1
                i += 1
            if linc > 0 and ldec > 0:
                res = max(res, i - st + 1)
            while i < n - 1 and a[i] == a[i + 1]:
                i += 1
        return res if res >= 0 else 0

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

Đầu vào

[8, 2, 4, 6, 3, 1]

Đầu ra

5