Pythonで指定された数値のセットを使用して式の可能な最大値を見つけるプログラム

nums1とnums2という2つの配列があり、それらの要素数が同じ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

これを解決するには、次の手順に従います-

• vs：=範囲0からnums1-1のサイズの各iのペア（nums1 [i]、nums2 [i]）のリスト
• vs：=vsの各vのv[1] /v[0]のtan-inverseによる並べ替え
• 最高：=0
• 範囲0からvs-1のサイズのiの場合、実行
  • u：=vs [i]
  • l：=u [0] * u [0] + u [1] * u [1]
  • インデックスi+1から（vs-1のi+サイズ）までのvsとvsの連結リスト内の各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：=vs [i]
  • l：=u [0] * u [0] + u [1] * u [1]
  • vsとvsの連結リストを逆にした各vについて、インデックスi +1からvs-1のi+サイズまで]、実行します
    • 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