สมมติว่าเรามีสองอาร์เรย์ที่เรียกว่า nums1 และ nums2 พวกมันมีจำนวนองค์ประกอบเท่ากัน N ตอนนี้ให้พิจารณาชุด S ที่มีองค์ประกอบ N ตั้งแต่ 1 ถึง N เราต้องหาค่าของ (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
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- vs :=รายการคู่ (nums1[i], nums2[i]) สำหรับแต่ละ i ในช่วง 0 ถึงขนาดของ nums1 - 1
- vs :=sort เทียบกับ tan-inverse ของ v[1]/v[0] สำหรับแต่ละ v in vs
- ดีที่สุด :=0
- สำหรับฉันในช่วง 0 ถึงขนาดของ vs - 1 ทำ
- u :=vs[i]
- l :=u[0]*u[0]+u[1]*u[1]
- สำหรับแต่ละ v ในรายการที่ต่อกันของ vs และ vs อีกครั้ง จากดัชนี i+1 ถึง (ขนาด i+ ของ vs - 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> ดีที่สุดแล้ว
- ดีที่สุด :=l
- u :=vs[i]
- l :=u[0]*u[0]+u[1]*u[1]
- สำหรับ v แต่ละรายการย้อนกลับรายการที่ต่อกันของ vs และ vs อีกครั้งจากดัชนี i+1 ถึง i+ ขนาด vs -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
