Dãy con tăng dần độ dài 3 (Increasing Triplet Subsequence) trong Python

Giả sử có một mảng chưa sắp xếp. Chúng ta phải kiểm tra xem có tồn tại dãy con tăng dần độ dài 3 hay không trong mảng đó.

Chính thức, hàm nên:

• Trả về true nếu tồn tại i, j, k
• sao cho arr[i] < arr[j] < arr[k] với 0 ≤ i < j < k ≤ n-1, ngược lại trả về false.

Để giải quyết, chúng ta làm theo các bước sau:

• Khởi tạo nho = vô cùng, lon = vô cùng.

• Duyệt qua từng phần tử i trong mảng:

  • Nếu i <= nho, thì nho = i.
  • Ngược lại nếu i <= lon, thì lon = i.
  • Ngược lại trả về true.

• Trả về false.

Ví dụ

class Solution(object):
    def increasingTriplet(self, nums):
        nho, lon = float('inf'), float('inf')
        for i in nums:
            if i <= nho:
                nho = i
            elif i <= lon:
                lon = i
            else:
                return True
        return False

ob1 = Solution()
print(ob1.increasingTriplet([5,3,8,2,7,9,4]))

Đầu vào

[5,3,8,2,7,9,4]

Đầu ra

True