[LeetCode] 1043. Partition Array for Maximum Sum

1043. Partition Array for Maximum Sum

풀이

처음 풀때 문제 이해가 안가서 죽는줄 알았다...
문제가 백준의 최솟값 찾기와 같은 문제인 줄 알고 오래 해맸다.
개인적으로 이문제가 더 어려운것 같았다.

과정

1. 순서별로 arr에 순회한다.(i)
2. i부터 i-k까지 역순회한다.(idx)
3. i~idx중 최댓값을 찾고 그 값이 선택된 만큼의 누적값과 현재값 중 큰값을 선택한다.

코드

import java.util.*;
class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int[] dp = new int[arr.length];
        for(int i = 0 ; i < arr.length; i ++){
            int max = 0;
            for(int j= 1; j < k + 1; j ++){
               int idx = i - j + 1;
               if (idx < 0){
                   continue;
               }
               max = Math.max(max, arr[idx]);
               if (idx == 0){
                   dp[i] = Math.max(dp[i], max * j);
                   continue;
               }
               dp[i] = Math.max(dp[i], dp[idx - 1] + max * j);
            }
        }
        return dp[arr.length - 1];
    }
}