문제설명
Given an integer array arr, partition the array into (contiguous) subarrays of length at most k. After partitioning, each subarray has their values changed to become the maximum value of that subarray.
Return the largest sum of the given array after partitioning. Test cases are generated so that the answer fits in a 32-bit integer.
이 문제는 정수 배열 arr이 주어졌을 때, 배열을 연속된 부분 배열들로 나누고 각 부분 배열의 길이를 최대 k로 제한합니다. 그 후에 각 부분 배열의 값들을 해당 부분 배열의 최댓값으로 변경합니다. 마지막으로, 변경된 배열의 모든 원소들을 합산한 값 중에서 최댓값을 찾아야 합니다.
간단히 말하면, 주어진 배열을 최대 길이가 k인 부분 배열로 나누고 각 부분 배열의 값들을 해당 부분 배열의 최댓값으로 바꾼 후, 이렇게 변환된 배열의 원소들을 모두 더한 값 중에서 최댓값을 구하는 문제입니다. 최종적으로 구해진 최댓값은 32비트 정수 범위에 들어간다는 조건이 주어져 있습니다.
입출력 예
Example 1:
Input: arr = [1,15,7,9,2,5,10], k = 3
Output: 84
Explanation: arr becomes [15,15,15,9,9,9,10]Example 2:
Input: arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
Output: 83
Example 3:
Input: arr = [1], k = 1
Output: 1
Constraints:
- 1 <= arr.length <= 500
- 0 <= arr[i] <= 109
- 1 <= k <= arr.length
코드 설명
이 문제의 핵심은 각 원소를 기준으로 최대 길이가 k인 부분 배열을 만들어가면서, 해당 부분 배열의 값을 최댓값으로 바꾸고 그 값을 이용하여 최대 합을 계산하는 것입니다. 이를 위해 동적 프로그래밍을 사용합니다.
1. dp 배열
int[] dp = new int[n];dp 배열은 각 인덱스 i에 해당하는 값이 배열의 처음부터 i까지 고려했을 때의 최대 합을 저장하는 배열입니다.
2. 이중 반복문
for (int i = 0; i < n; i++) { // 배열의 각 원소에 대해서 반복
for (int j = 1; j <= k && i - j + 1 >= 0; j++) {
// 최대 길이가 k인 부분 배열을 만들기 위한 반복문
// 현재 원소로부터 역방향으로 j개의 원소를 포함한 부분 배열을 만들어봄
}
}바깥쪽 반복문(for (int i = 0; i < n; i++)) : 배열의 각 원소에 대해 처리합니다. 안쪽 반복문에서 현재 원소를 기준으로 최대 길이가 k인 부분 배열을 만들어가면서 최대 합을 계산합니다.
안쪽 반복문(for (int j = 1; j <= k && i - j + 1 >= 0; j++)) : 현재 원소로부터 역방향으로 최대 길이가 k인 부분 배열을 만듭니다. j는 현재 부분 배열의 길이를 나타냅니다.
3. 최댓값 갱신
max = Math.max(max, arr[i - j + 1]);부분 배열을 만들면서 최댓값을 찾아 max 변수에 저장합니다. 이를 통해 부분 배열의 값을 최댓값으로 변경합니다.
4. dp 값 업데이트
dp[i] = Math.max(dp[i], (i >= j ? dp[i - j] : 0) + max * j);dp[i]는 현재 원소를 기준으로 만들어진 부분 배열의 최대 합을 나타냅니다. 이 값은 이전에 계산된 최대 합과 현재 부분 배열의 최대값(max)을 이용하여 업데이트됩니다.
5. 최종 반환
return dp[n - 1];dp[n - 1]은 마지막 원소까지 고려했을 때의 최대 합을 나타냅니다. 이 값을 반환합니다.
6. 간단한 예시
배열: [1, 4, 1, 5, 7, 3, 6, 1]
최대 길이 k: 3
배열의 첫 번째 원소 1부터 시작하여 최대 길이가 3인 부분 배열을 만들고, 각 부분 배열의 값을 부분 배열의 최댓값으로 변경합니다.
첫 번째 부분 배열: [1, 4, 1], 최댓값 4로 변경 → 합: 4 * 3 = 12
두 번째 부분 배열: [4, 1, 5], 최댓값 5로 변경 → 합: 5 * 3 = 15
세 번째 부분 배열: [1, 5, 7], 최댓값 7로 변경 → 합: 7 * 3 = 21
그 외의 부분 배열도 같은 방식으로 계산하고, 각 부분 배열의 합을 누적하여 최종적으로 마지막 원소까지 고려했을 때의 최대 합을 구합니다.
소스코드&결과
소스코드
import java.util.Arrays;
class Solution {
public int maxSumAfterPartitioning(int[] arr, int k) {
int n = arr.length; // 배열의 길이를 n에 저장
int[] dp = new int[n]; // 동적 프로그래밍을 위한 배열 dp 생성
for (int i = 0; i < n; i++) { // 배열의 각 원소에 대해서 반복
int max = arr[i]; // 현재 원소를 최댓값으로 초기화
for (int j = 1; j <= k && i - j + 1 >= 0; j++) {
// 최대 길이가 k인 부분 배열을 만들기 위한 반복문
// 현재 원소로부터 역방향으로 j개의 원소를 포함한 부분 배열을 만들어봄
max = Math.max(max, arr[i - j + 1]); // 최댓값 갱신
// 현재 부분 배열의 최댓값을 구하고, 이를 이용하여 dp 값을 업데이트
dp[i] = Math.max(dp[i], (i >= j ? dp[i - j] : 0) + max * j);
}
}
return dp[n - 1]; // 마지막 원소까지 고려한 최댓값 반환
}
}결과
