Python의 최대 합을 위한 파티션 배열

<시간/>

정수 배열 A가 있다고 가정하고 배열을 길이가 최대 K인 (인접한) 하위 배열로 분할해야 합니다. 분할 후 각 하위 배열의 값은 해당 하위 배열의 최대값이 되도록 변경됩니다. 파티셔닝 후에 주어진 배열의 가장 큰 합을 찾아야 합니다. 따라서 입력이 [1, 15, 7, 9, 2, 5, 10]이고 k =3이면 출력은 84가 됩니다. 이는 배열이 [15, 15, 15, 9, 10, 10이 되기 때문입니다. , 10]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

A와 같은 길이의 배열 dp 하나를 만들고 0으로 채웁니다.
0에서 A - 1까지의 범위에 있는 i의 경우
- dp[i] =A[i] + dp[i - 1] if i – 1>=0 그렇지 않으면 0
- temp :=A[i]
- 1 ~ k – 1 범위의 j에 대해
  - i – j>=0
    - 인덱스 :=i – j
    - 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