99클럽 코테 스터디 18일차 TIL, DP(Partition Array for Maximum Sum)

1. 문제 정의

2. 문제 접근

dp 토픽에 속한 것이니 dp로 풀면 될 것 같다.

3. 문제 풀이

1. k길이 만큼의 window가 필요하고, 이 window를 sliding하면서 for-loop의 각 시점마다 최대값을 알아낸다.
2. 이전 dp 배열에 내가 알아낸 최댓값을 곱해주고 더해준다.
3. 마지막 인덱스의 값을 리턴한다.

4. 코드

class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int length = arr.length;
        int[] dp = new int[length + 1];
        for (int i = 1; i <= length; i++) {
            int max = 0;
            int sum = 0;
            for (int j = 1; j <= k && i - j >= 0; j++) {
                max = Math.max(max, arr[i - j]);
                sum = Math.max(sum, (max * j) + dp[i - j]);
            }
            dp[i] = sum;
        }
        return dp[length];
    }
}

 

 

 

5. 회고

문제부터가 이해가 되지 않아서 이해하는데 한참이 걸렸다... 아직도 사실 문제를 100퍼센트 이해하진 못했지만 여러 유튜브들의 해설 영상을 보고 조금은 이해가? 된 것 같다... 다시 혼자서 풀 수 있을때까지 연습해야지...