Pythonで合計を最大化するためのパーティション配列

整数配列Aがあるとすると、配列を最大Kの長さの（連続した）サブ配列に分割する必要があります。分割後、各サブ配列の値は、そのサブ配列の最大値になるように変更されます。パーティション分割後、指定された配列の最大の合計を見つける必要があります。したがって、入力が[1、15、7、9、2、5、10]のようで、k =3の場合、出力は84になります。これは、配列が[15、15、15、9、10、10 、10]

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

• Aと同じ長さの配列dpを1つ作成し、これを0で埋めます
• 0からA-1の長さの範囲のiの場合
  • dp [i] =A [i] + dp [i-1]（i – 1> =0の場合）それ以外の場合は0
  • temp：=A [i]
  • 1からk–1の範囲のjの場合
    • if i – j> =0
      • インデックス：=i – j
      • temp：=tempとA[i--j]の最大値
      • インデックス– 1> =0の場合、
        • dp [i]：=dp [i]の最大値と（temp *（i – index + 1）+ dp [index-1]）
      • それ以外の場合、dp [i]：=dp[i]と0の最大値
• dpの最後の要素を返す

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

例

class Solution(object):
   def maxSumAfterPartitioning(self, A, K):
      dp = [0 for i in range(len(A))]
      for i in range(len(A)):
         dp[i] = A[i] + (dp[i-1] if i-1>=0 else 0)
         temp = A[i]
         for j in range(1,K):
            if i-j>=0:
               index = i-j
               temp = max(temp,A[i-j])
               dp[i] = max(dp[i],temp*(i-index+1) + (dp[index-1] if index-1 >=0 else 0))
      return dp[-1]
ob = Solution()
print(ob.maxSumAfterPartitioning([1,15,7,9,2,5,10],3))

入力

[1,15,7,9,2,5,10]
3

出力

84