1043

1043. Partition Array for Maximum Sum

Medium

32138 FavoriteShare

Given an integer array A, you partition the array into (contiguous) subarrays of length at most K.  After partitioning, each subarray has its values changed to become the maximum value of that subarray.

Return the largest sum of the given array after partitioning.

 

Example 1:

Input: A = [1,15,7,9,2,5,10], K = 3 Output: 84 Explanation: A becomes [15,15,15,9,10,10,10]

 

 

DP 문제이다.

 

DP 배열의 len이 Array 보다 1이 더 높은 이유는 

 

0이라는 buffer 때문이다. 

 

그래서 Return 할 때는 그 전 단계를 return N-1이다. 

 

그림으로 이렇게 예제로 풀면 잘 풀린다. 재밌는 문제이다.