Pythonで重複しない2つのサブリストの最大合計を見つけるプログラム

numsと呼ばれる数値のリストと2つの値xおよびyがあるとすると、長さxおよびyを持つnums内の重複しない2つのサブリストの最大合計を見つける必要があります。

したがって、入力がnums =[3、2、10、-2、7、6] x =3 y =1の場合、出力は22になります。これは、長さが3のサブリストとして[3、2、 10]と、その他には[7]を選択します。

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

• P：=単一要素0のリスト
• Aのxごとに、
  • Pの最後に（P + xの最後の要素）を挿入します
• 関数solve（）を定義します。これにはlen1、len2が必要です
• Q：=範囲0からP-len1のサイズまでの各iの要素（P [i + len1]-P [i]）を含むリスト
• プレフィックス：=Qのコピー
• 0からプレフィックス-1のサイズまでの範囲のiの場合、do
  • prefix [i + 1]：=プレフィックス[i+1]とプレフィックス[i]の最大値
• ans：=-infinity
• len1からP-len2のサイズの範囲のiの場合、
  • 左：=プレフィックス[i-len1]
  • 右：=P [i + len2]-P [i]
  • ans：=ansの最大値と（左+右）
• 回答を返す
• メインの方法から次のようにします-
• solve（len1、len2）、solve（len2、len1）の最大値を返す

理解を深めるために、次の実装を見てみましょう-

例

class Solution:
   def solve(self, A, len1, len2):
      P = [0]
      for x in A:
         P.append(P[-1] + x)
      def solve(len1, len2):
         Q = [P[i + len1] - P[i] for i in range(len(P) - len1)]
         prefix = Q[:]
         for i in range(len(prefix) - 1):
            prefix[i + 1] = max(prefix[i + 1], prefix[i])
            ans = float("-inf")
            for i in range(len1, len(P) - len2):
               left = prefix[i - len1]
               right = P[i + len2] - P[i]
            ans = max(ans, left + right)
            return ans
         return max(solve(len1, len2), solve(len2, len1))
ob = Solution()
nums = [3, 2, 10, -2, 7, 6]
x = 3
y = 1
print(ob.solve(nums, x, y))

入力

[3, 2, 10, -2, 7, 6], 3, 1

出力

22