99클럽 코테 스터디 14일차 TIL [LeetCode] Partition Array for Maximum Sum (Java)

문제

[LeetCode] Partition Array for Maximum Sum

풀이

배열을 분할하여 각 분할의 최대값 합을 최대화하는 문제

• arr을 순회하며 k 범위 내의 최대값을 추적한다.
• 해당 인덱스까지의 최적의 결과를 dp에 저장한다.

정답 코드

public class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        int[] dp = new int[n];

        for (int i = 0; i < n; i++) {
            int max = 0;
            for (int j = 1; j <= k && i - j + 1 >= 0; j++) {
                max = Math.max(max, arr[i - j + 1]);
                dp[i] = Math.max(dp[i], (i - j >= 0 ? dp[i - j] : 0) + max * j);
            }
        }

        return dp[n - 1];
    }
}