3381. Maximum Subarray Sum With Length Divisible by K

Leetcode link

题目简介

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */

题目给我们一个数字数组 nums 以及一个数字 k

要求我们求出和最大且长度可以被 k 整除的 nums 的子数组，并返回其子数组和

解题思路

想要求长度可以被 k 整除的子数组，除了找 k 的倍数长度的数组之外，还可以用两个长度对 k 同余的子数组相减获得

为了达到题目的目的，我们就必须记录余数为 0~k-1 长度的子数组的最小和 kSum

这样一来只要当前子数组长度余数为 i，我们可以用子数组 subArray - kSum[i] 获得当前长度数组的最大和

Javascript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maxSubarraySum = function (nums, k) {
    let prefixSum = 0
    let maxSum = Number.MIN_SAFE_INTEGER
    const kSum = new Array(k).fill(Number.MAX_SAFE_INTEGER / 2)
    // kSum[k - 1] stands for the subarray's min sum whose length % k === 0
    kSum[k - 1] = 0

    for (let i = 0; i < nums.length; i++) {
        prefixSum += nums[i]
        maxSum = Math.max(maxSum, prefixSum - kSum[i % k])
        kSum[i % k] = Math.min(kSum[i % k], prefixSum)
    }
    return maxSum
};