Python程式：使用給定數字集查詢表示式的最大可能值

假設我們有兩個名為nums1和nums2的陣列，它們具有相同數量的元素N。現在考慮一個集合S，其中包含從1到N的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 := 對於每個i從0到nums1的大小-1，建立一個(nums1[i]，nums2[i])的配對列表
  • vs := 對於每個v in vs，根據v[1]/v[0]的反正切對vs進行排序
  • best := 0
  • 對於i從0到vs的大小-1，執行以下操作：
    • u := vs[i]
    • l := u[0]*u[0]+u[1]*u[1]
    • 對於vs和vs從索引i+1到(i+ vs的大小-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 > best，則
      • best := l
    • u := vs[i]
    • l := u[0]*u[0]+u[1]*u[1]
    • 對於vs和vs從索引i+1到i+ vs的大小-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 > best，則
  • 返回best

示例

讓我們看看以下實現以獲得更好的理解：

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

更新時間: 2021年10月11日

277 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告