Chương trình tìm giá trị lớn nhất của biểu thức dùng tập số cho trước trong Python

Giả sử chúng ta có hai mảng nums1 và nums2, cùng chứa N phần tử. Xét tập S gồm N phần tử từ 1 đến N. Ta cần tìm giá trị lớn nhất của biểu thức (nums1[i1] + nums1[i2] + ... + nums1[ik])² + (nums2[i1] + nums2[i2] + ... + nums2[ik])² với {i1, i2, ... ik} là tập con không rỗng của S.

Ví dụ, với nums1 = [-1, 6], nums2 = [5, 4], kết quả là 106 vì:

• (-1)² + 5² = 26
• 6² + 4² = 50
• (-1 + 6)² + (5 + 4)² = 106

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

1. Tạo danh sách cặp vs = [(nums1[i], nums2[i])] cho mọi i
2. Sắp xếp vs theo góc cực tính atan2(v[1], v[0])
3. Khởi tạo best = 0
4. Với mỗi chỉ số i:
   • Lấy u = vs[i], tính l = u[0]² + u[1]²
   • Duyệt các phần tử trong (vs + vs)[i+1 : i+len(vs)] (xét vòng tròn):
     • Tính tổng vector t1 = (u[0]+v[0], u[1]+v[1])
     • Nếu t1[0]² + t1[1]² >= l thì cập nhật u = t1, l = t1[0]² + t1[1]²
   • Cập nhật best = max(best, l)
   • Lặp lại quá trình trên nhưng duyệt theo chiều ngược lại
5. Trả về best

Ví dụ minh họa

from math import atan2

def solve(nums1, nums2):
    vs = list(zip(nums1, nums2))
    vs = sorted(vs, key=lambda v: atan2(v[1], v[0]))
    best = 0
    for i in range(len(vs)):
        u = vs[i]
        l = u[0]*u[0] + u[1]*u[1]
        for v in (vs + vs)[i+1:(i+len(vs))]:
            t1 = (u[0]+v[0], u[1]+v[1])
            t2 = t1[0]*t1[0] + t1[1]*t1[1]
            if t2 >= l:
                u = t1
                l = t2
        if l > best:
            best = l
        u = vs[i]
        l = u[0]*u[0] + u[1]*u[1]
        for v in reversed((vs + vs)[i+1:(i+len(vs))]):
            t1 = (u[0]+v[0], u[1]+v[1])
            t2 = t1[0]*t1[0] + t1[1]*t1[1]
            if t2 >= l:
                u = t1
                l = t2
        if l > best:
            best = l
    return best

nums1 = [-1, 6]
nums2 = [5, -4]
print(solve(nums1, nums2))

Đầu vào

[-1, 6], [5, -4]

Đầu ra

52