Chương trình đếm số dãy con thỏa mãn điều kiện tổng min + max ≤ k bằng Python

Cho mảng nums và giá trị k. Đếm số dãy con không rỗng sao cho tổng của phần tử nhỏ nhất và lớn nhất trong dãy con đó ≤ k. Kết quả modulo 10^9 + 7.

Ví dụ: nums = [4,6,7,8], k = 11. Kết quả 4: các dãy con [4], [4,6], [4,6,7], [4,7] đều thỏa 4+max ≤ 11.

Thuật toán giải quyết (Hai con trỏ)

• Sắp xếp nums.
• m := 10^9 + 7.
• left := 0, right := n-1, res := 0.
• Khi left ≤ right:
  • Nếu nums[left] + nums[right] > k: right -= 1 (giảm max).
  • Ngược lại: mọi dãy con bắt đầu tại left và kết thúc tại bất kỳ chỉ số nào từ left đến right đều thỏa mãn (vì mảng đã sắp xếp). Số dãy con như vậy là 2^(right-left). Cộng vào res: res = (res + 2^(right-left)) % m. left += 1.
• Trả về res.

Ví dụ triển khai

def solve(nums, k):
    nums.sort()
    m = 10**9 + 7
    left = 0
    right = len(nums) - 1
    res = 0
    while left <= right:
        if nums[left] + nums[right] > k:
            right -= 1
        else:
            num_inside = right - left
            res = (res + pow(2, num_inside, m)) % m
            left += 1
    return res

nums = [4,6,7,8]
k = 11
print(solve(nums, k))

Đầu vào

[4,6,7,8], 11

Đầu ra

4