পাইথনে দिये गये সংখ্যা সেট ব্যবহার করে এক্সপ্রেশনের সর্বোচ্চ সম্ভাব্য মান বের করার প্রোগ্রাম

দুটি অ্যারে nums1 এবং nums2 দেওয়া আছে, যাদের উপাদান সংখ্যা সমান N। সেট S আছে 1 থেকে N পর্যন্ত। আমাদের খুঁজে বের করতে হবে (Σ nums1[i])² + (Σ nums2[i])² এর সর্বোচ্চ মান, যেখানে {i1, i2, ... ik} হলো S-এর একটি নন-খালি সাবসেট।

উদাহরণ

nums1 = [-1, 6], nums2 = [5, 4] → আউটপুট: 106

• (-1)² + 5² = 26
• 6² + 4² = 50
• (-1+6)² + (5+4)² = 106 (সর্বোচ্চ)

এলগরিদম

1. vs := [(nums1[i], nums2[i]) for i in range(N)]
2. vs-কে atan2(v[1], v[0]) অনুযায়ী সর্ট করুন।
3. best := 0
4. প্রতিটি i এর জন্য:
   • u := vs[i], l := u[0]² + u[1]²
   • (vs+vs)[i+1 : i+len(vs)] এর প্রতিটি v এর জন্য:
     • t1 := (u[0]+v[0], u[1]+v[1])
     • t2 := t1[0]² + t1[1]²
     • যদি t2 >= l: u := t1, l := t2
   • best = max(best, l)
   • উপরের প্রসেসটি রিভার্স অর্ডারে আবার दुহরান।
5. best রিটার্ন করুন।

পাইথন কোড

from math import atan2

def solve(nums1, nums2):
    vs = list(zip(nums1, nums2))
    vs.sort(key=lambda v: atan2(v[1], v[0]))
    best = 0
    n = len(vs)
    for i in range(n):
        u = vs[i]
        l = u[0]*u[0] + u[1]*u[1]
        for v in (vs+vs)[i+1:i+n]:
            t1 = (u[0]+v[0], u[1]+v[1])
            t2 = t1[0]*t1[0] + t1[1]*t1[1]
            if t2 >= l:
                u, l = t1, 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+n]):
            t1 = (u[0]+v[0], u[1]+v[1])
            t2 = t1[0]*t1[0] + t1[1]*t1[1]
            if t2 >= l:
                u, l = t1, t2
        if l > best:
            best = l
    return best

nums1 = [-1, 6]
nums2 = [5, -4]
print(solve(nums1, nums2))  # আউটপুট: 52

ইনপুট / আউটপুট

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