पायथन में दी गई संख्याओं के सेट से एक्सप्रेशन का अधिकतम संभव मान ढूंढना

मान लीजिए हमारे पास दो ऐरे nums1 और nums2 हैं, जिनमें समान संख्या में तत्व N हैं। अब 1 से N तक के तत्वों का एक सेट S लें। हमें (nums1[i1] + nums1[i2] + ... nums1[ik])² + (nums2[i1] + nums2[i2] + ... nums2[ik])² का मान ढूंढना है, जहां {i1, i2, ... ik} सेट S का एक नॉन-खाली सबसेट है।

उदाहरण के लिए, यदि इनपुट है nums1 = [-1, 6], nums2 = [5, 4], तो आउटपुट होगा 106 क्योंकि:

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

समाधान दृष्टिकोण

यह समस्या ज्यामितीय व्याख्या पर आधारित है। प्रत्येक जोड़ी (nums1[i], nums2[i]) को 2D तल पर एक वेक्टर माना जाता है। लक्ष्य इन वेक्टरों के एक सबसेट का चयन करना है ताकि उनके योग की परिमाण (magnitude) अधिकतम हो।

सभी जोड़ियों को (nums1[i], nums2[i]) के रूप में सूचीबद्ध करें।
इन जोड़ियों को उनके ध्रुवीय कोण (polar angle) के अनुसार सॉर्ट करें, atan2(y, x) का उपयोग करके।
सर्कुलर ऐरे तकनीक का उपयोग करके सभी संभावित लगातार सबसेट्स की जांच करें (ऐरे को दोहराकर)।
फॉरवर्ड और बैकवर्ड दोनों दिशाओं में अधिकतम वर्ग परिमाण ट्रैक करें।

पायथन कार्यान्वयन

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))

इनपुट

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