ปัญหา
ให้อาร์เรย์ nums (มีทั้งบวกและลบ) และค่า k ตรวจสอบว่ามี subarray ติดต่อกันที่ผลคูณเท่ากับ k หรือไม่
ตัวอย่าง
nums = [-2, -1, 1, 3, 5, 8], k = 6 → subarray [-2, -1, 3] ผลคูณ = 6 → True
แนวคิดการแก้ปัญหา (Kadane แบบผลคูณ)
เก็บ max_prod และ min_prod จนถึง index ปัจจุบัน (เพราะลบ×ลบ = บวก)
- เจอตัวลบ → สลับ max/min
- อัปเดต max/min ด้วย max/min(num, max*num, min*num)
- ถ้า max หรือ min เท่ากับ k → True
โค้ดตัวอย่าง
def solve(nums, k):
max_prod = min_prod = nums[0]
if max_prod == k:
return True
for num in nums[1:]:
if num < 0:
max_prod, min_prod = min_prod, max_prod
max_prod = max(num, max_prod * num)
min_prod = min(num, min_prod * num)
if max_prod == k or min_prod == k:
return True
return False
print(solve([-2, -1, 1, 3, 5, 8], 6)) # True
อินพุต / เอาต์พุต
Input: [-2,-1,1,3,5,8], 6 Output: True
