Kiểm tra tồn tại mảng con có tích bằng K trong Python

Cho mảng nums chứa số dương và âm, và một giá trị k. Kiểm tra xem có tồn tại mảng con liên tiếp nào có tích bằng k hay không.

Ví dụ: nums = [-2,-1,1,3,5,8], k = 6 → mảng con [-2,-1,3] tích = 6 → True.

Giải thuật

• Theo dõi tích lớn nhất và nhỏ nhất kết thúc tại vị trí hiện tại (do có số âm).
• Khi gặp số âm, hoán đổi max và min.
• Cập nhật max/min bằng max/min của phần tử hiện tại và tích với max/min trước.
• Nếu max hoặc min bằng k → True.

Mã ví dụ

def solve(nums, k):
    minimum = nums[0]
    maximum = nums[0]
    prod_max = nums[0]
    for i in range(1, len(nums)):
        if nums[i] < 0:
            maximum, minimum = minimum, maximum
        maximum = max(nums[i], maximum * nums[i])
        minimum = min(nums[i], minimum * nums[i])
        if minimum == k or maximum == k:
            return True
        prod_max = max(prod_max, maximum)
    return False

nums = [-2,-1,1,3,5,8]
k = 6
print(solve(nums, k))

Đầu vào

[-2,-1,1,3,5,8], 6

Đầu ra

True