Tìm cặp từ mảng cho giá trị nCr lớn nhất trong Python

Cho một mảng arr gồm n số nguyên, ta cần tìm arr[i] và arr[j] sao cho arr[i]Carr[j] (tổ hợp chập arr[j] của arr[i]) là lớn nhất có thể. Nếu có nhiều cặp, trả về bất kỳ cặp nào.

Ví dụ, nếu đầu vào là [4, 1, 2], kết quả sẽ là 4 2 vì 4C1 = 4, 4C2 = 6 và 2C1 = 2, nên cặp (4,2) là cặp cần tìm.

Thuật toán giải quyết

• Sắp xếp mảng v.
• N := v[n - 1] (phần tử lớn nhất).
• Nếu N lẻ:
  • first := N // 2, second := first + 1.
  • Khởi tạo left := -1, right := -1, temp := -1, res1 := 3 * 10¹⁸.
  • Duyệt i từ 0 đến n-1:
    • Nếu v[i] > first: temp := i, thoát vòng lặp.
    • Ngược lại: difference := first - v[i]. Nếu difference < res1 thì cập nhật res1 và left := v[i].
  • right := v[temp].
  • difference1 := first - left, difference2 := right - second.
  • Nếu difference1 < difference2 in N, left, ngược lại in N, right.
• Ngược lại (N chẵn):
  • max := N // 2, res := 3 * 10¹⁸, R := -1.
  • Duyệt i từ 0 đến n-2:
    • difference := abs(v[i] - max).
    • Nếu difference < res: cập nhật res và R := v[i].
  • In N, R.

Ví dụ minh họa

def findMatrixPair(v, n):
    v.sort()
    N = v[n - 1]
    if N % 2 == 1:
        first = N // 2
        second = first + 1
        res1, res2 = 3 * (10 ** 18), 3 * (10 ** 18)
        left, right = -1, -1
        temp = -1
        for i in range(0, n):
            if v[i] > first:
                temp = i
                break
            else:
                difference = first - v[i]
                if difference < res1:
                    res1 = difference
                    left = v[i]
        right = v[temp]
        difference1 = first - left
        difference2 = right - second
        if difference1 < difference2:
            print(N, left)
        else:
            print(N, right)
    else:
        max_val = N // 2
        res = 3 * (10 ** 18)
        R = -1
        for i in range(0, n - 1):
            difference = abs(v[i] - max_val)
            if difference < res:
                res = difference
                R = v[i]
        print(N, R)

v = [4, 1, 2]
n = len(v)
findMatrixPair(v, n)  # Output: 4 2

Đầu vào

[4,1,2], 3

Đầu ra

4 2