题目描述

给你一个整数数组 nums 和一个整数 k。

返回 nums 中一个 非空子数组 的 最大 和，要求该子数组的长度可以 被 k 整除。

子数组 是数组中一个连续的、非空的元素序列。

样例

输入： nums = [1,2], k = 1

输出： 3

解释：

子数组 [1, 2] 的和为 3，其长度为 2，可以被 1 整除。

输入： nums = [-1,-2,-3,-4,-5], k = 4

输出： -10

解释：

满足题意且和最大的子数组是 [-1, -2, -3, -4]，其长度为 4，可以被 4 整除。

输入： nums = [-5,1,2,-3,4], k = 2

输出： 4

解释：

满足题意且和最大的子数组是 [1, 2, -3, 4]，其长度为 4，可以被 2 整除。

限制

• 1 <= k <= nums.length <= 2 * 10^5
• -10^9 <= nums[i] <= 10^9

算法

(分组前缀和) $O(n)$

1. 定义一个长度为 $k$ 的数组 $p$，$p(i)$ 存储长度模 $k$ 的余数为 $i$ 时的前缀和的最小值。初始时，$p(0) = 0$。
2. 遍历数组（下标从 $1$ 开始），当 $i \ge k$ 时，可以用当前的前缀和，减去 $p(i \text{ MOD } k)$ 来更新答案。然后更新 $p(i \text{ MOD } k)$ 的最小值。

时间复杂度

• 遍历数组一次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(k)$ 的额外空间存储分组前缀和。

C++ 代码

#define LL long long

class Solution {
public:
    LL maxSubarraySum(vector<int>& nums, int k) {
        const int n = nums.size();

        vector<LL> p(k, INT64_MAX);
        p[0] = 0;

        LL sum = 0, ans = INT64_MIN;
        for (int i = 1; i <= n; i++) {
            sum += nums[i - 1];

            if (i >= k)
                ans = max(ans, sum - p[i % k]);

            p[i % k] = min(p[i % k], sum);
        }

        return ans;
    }
};