Chương trình tìm tổng lớn nhất của cặp số nhỏ hơn target Python

Cho mảng nums và giá trị target. Tìm tổng lớn nhất của cặp số trong nums mà tổng (tức là ≤ target-1).

Ví dụ: nums=[8,3,4,9,2], target=8 → 7 (4+3=7).

Giải thuật (Sắp xếp + Hai con trỏ)

1. Sắp xếp nums
2. p1=0 (đầu), p2=len(nums)-1 (cuối), m=-inf
3. Khi :
   • Nếu nums[p1] + nums[p2] < target: cập nhật m = max(m, sum), p1++
   • Ngược lại: p2--
4. Trả về m

Ví dụ triển khai

import math

def solve(nums, target):
    nums.sort()
    p1, p2 = 0, len(nums) - 1
    m = -math.inf
    while p1 < p2:
        s = nums[p1] + nums[p2]
        if s < target:
            m = max(m, s)
            p1 += 1
        else:
            p2 -= 1
    return m

print(solve([8, 3, 4, 9, 2], 8))

Đầu vào

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

Đầu ra

7