ধরুন আমাদের কাছে nums1 এবং nums2 নামক দুটি অ্যারে রয়েছে, তাদের একই সংখ্যক উপাদান N রয়েছে। এখন 1 থেকে N পর্যন্ত N উপাদান সহ একটি সেট S বিবেচনা করুন। আমাদের (nums1[i1] + nums1[i2] + এর মান খুঁজে বের করতে হবে। .. nums1[ik])^2 + (nums2[i1] + nums2[i2] + ... nums2[ik])^2 যেখানে {i1, i2, ... ik} হল S সেটের খালি উপসেট নয় .
সুতরাং, যদি ইনপুট হয় nums1 =[-1, 6] nums2 =[5, 4], তাহলে আউটপুট হবে 106 কারণ
- (-1)^2 + (5)^2 =26
- (6)^2 + (4)^2 =50
- (-1 + 6)^2 + (5 + 4)^2 =106
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- বনাম :=জোড়ার একটি তালিকা (সংখ্যা 1[i], সংখ্যা2[i]) 0 থেকে সংখ্যা 1 - 1 এর আকারের প্রতিটি i এর জন্য
- বনাম :=প্রতিটি v এর জন্য v[1]/v[0] এর ট্যান-ইনভার্স অনুসারে বনাম সাজান
- সর্বোত্তম :=0
- আমি 0 থেকে বনাম - 1 এর পরিসরের জন্য, কর
- u :=বনাম[i]
- l :=u[0]*u[0]+u[1]*u[1] সূচী i+1 থেকে (i+ এর আকার বনাম - 1 পর্যন্ত) বনাম এবং বনাম এর সংযোজিত তালিকার প্রতিটি v-এর জন্য, করুন
- t1 :=(u[0]+v[0], u[1]+v[1])
- t2 :=t1[0]*t1[0]+t1[1]*t1[1]
- যদি t2>=l হয়, তাহলে
- u :=t1
- l :=t2
- যদি l> সেরা হয়, তাহলে
- সেরা :=l
- u :=বনাম[i]
- l :=u[0]*u[0]+u[1]*u[1]
- প্রতিটি v এর বিপরীতে বনাম এবং বনাম এর সংযোজিত তালিকা i+1 থেকে i+ আকারে বনাম -1], করুন
- t1 :=(u[0]+v[0], u[1]+v[1])
- t2 :=t1[0]*t1[0]+t1[1]*t1[1]
- যদি t2>=l হয়, তাহলে
- u :=t1
- l :=t2
- যদি l> সেরা হয়, তাহলে
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
from math import atan2 def solve(nums1, nums2): vs = 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]
আউটপুট
52