[Leetcode] 3381. Maximum Subarray Sum With Length Divisible by K

정수로 구성된 배열 nums와 자연수 k가 주어진다. 부분배열(Subarray)의 길이가 k 로 나누어지는 부분배열 중 제일 큰 배열의 합을 찾는 문제.

제약조건은 1 <= k <= nums.length <= 2 * 10^5 이므로 그리디하게 찾으면 O(N^2)이 되어서 안된다. 누적합과 구간합 둘 다 사용하면 최대 10^5 길이의 배열을 두 번 돌게 되므로 O(2N), 즉 O(N) 에 돌 수 있다.

구간의 길이를 L = i - j 라고 했을 때, i % k와 i % k의 값이 같고 i까지의 누적합(C[i]) - j를 만족하는 누적합 중 제일 작은 값(P[j]) 을 찾으면 된다.

const MAX_VALUE = Math.pow(10, 9) + 1
const MIN_VALUE = -Infinity;

function maxSubarraySum(nums: number[], k: number): number {
    const C = Array.from({ length: nums.length + 1 }, () => 0) // 누적합

    for (let i = 0; i < nums.length; i++) {
        C[i + 1] = C[i] + nums[i]
    }

    const P = Array.from({ length: k }, () => MAX_VALUE) // 최소구간합

    let maxValue = MIN_VALUE;

    P[0] = 0;

    for (let i = 1; i < nums.length + 1; i++) {
        const remainder = i % k;
        const currentMinPrefixSum = P[remainder];

        if (currentMinPrefixSum !== MAX_VALUE) {
            const newPrefixSum = C[i] - currentMinPrefixSum;
            maxValue = Math.max(maxValue, newPrefixSum);
        }

        P[remainder] = Math.min(P[remainder], C[i])
    }

    return maxValue;
};