3381. Maximum Subarray Sum With Length Divisible by K

오늘부터, LeetCode 풀어서 티셔츠 얻기 프로젝트를 시작해보겠다.

You are given an array of integers nums and an integer k.
Return the maximum sum of a subarray of nums, such that the size of the subarray is divisible by k.

배열 nums와 k가 주어진다. subarray 크기가 k로 나눠지고 원소합이 최대인 값을 찾아야한다.

일단 여기서 실수했다. k의 정의를 제대로 읽지않아서, 원소합이 k로 나눠져야하는 것으로 오인해 잘못 풀었다. 배열의 크기가 k로 나눠지는 게 올바른 해석이다.

또한 subarray의 정의를 보면 연속된 원소를 갖는다고 하니, 부분수열과는 다른 정의인 듯하다.

이제 어떻게 풀 건지 결정해야된다.

합을 다루니까 일단 누적합으로 접근했다. 그리고 k로 나눠지는 경우만 보면 되므로, 탐색을 k부터 해도 될 것이라고 판단했다.

배열 크기가 k의 배수가 될 수 있다. 이 경우에는 어떻게 해야될까? 무작정 배열 크기를 늘리는 게 아니라 배열 크기를 늘렸을 때 합이 커지는 지 확인하면 된다.

class Solution {
    public long maxSubarraySum(int[] nums, int k) {
        int n = nums.length;
        long[] pre = new long[n+1];
        for(int i=0; i<n; i++){
            pre[i+1] = pre[i] + nums[i];
        }
        long max = Long.MIN_VALUE;

        // i에서 끝나는 길이 k의 배수인 부분 수열 중 최대 합
        long[] dp = new long[n + 1];

        Arrays.fill(dp, Long.MIN_VALUE);

        for (int i = k; i <= n; i++) {
            long chunk = pre[i] - pre[i - k];

            if (i >= 2 * k) { // 이미 k이상 지나온 경우
                long before = dp[i-k];
                dp[i] = chunk + Math.max(0, before);
            } else {
                dp[i] = chunk;
            }

            max = Math.max(max, dp[i]);
        }
        // System.out.println(Arrays.toString(dp));
        return max;
    }
}

내가 항상 어려워하는 dp에 들어갈 값을 "i에서 끝나는 길이 k의 배수인 부분 수열 중 최대 합"으로 정의했다.

위 코드는 정답 코드지만, 한 가지 잘못해서 틀렸었다.

i >= 2 * k가 그 부분이다.

long before = dp[i-k];
if(before > 0){
    dp[i] = chunk + before;
}

만약에 직전 k배수 배열의 합이 음수라면 아예 고려하지않도록 조건을 설정했었는데, 그러면 [-10, -1], k=1인 경우를 처리하지 못하게 된다. 이전에 -10인데, 이러면 before가 음수라 dp[1] 위치에 -1을 넣지 않게 되는 것이다.

올바른 동작은 음수인 경우에 이전 before 값을 0으로 처리하는 것이다. 이러면 이전 값이 음수여도, 일단 현재 위치에서 값을 저장해 나중에 사용할 수 있게 된다.(음수+음수, 음수+양수 두 경우를 아예 신경쓰지 않는다. 그냥 분리된 경우로 보는 것)

res

Comments