정수 배열 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의 최대값
- i – j>=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