题目信息

题目描述

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

初步思路

  1. 使用前缀和技巧：pre[i] 表示前 i 个元素的和。
  2. 子数组 [i, j] 的和为 pre[j+1] - pre[i]，长度为 j - i + 1。
  3. 若长度能被 k 整除，则 (j - i + 1) % k == 0，即 (j - i) % k == k - 1。
  4. 对于每个位置 j，我们需要找到所有满足 (j - i) % k == 0 的 i（即 i % k == j % k），使得 pre[j+1] - pre[i] 最大。
  5. 维护每种余数 r = j % k 下的最小前缀和 min_s[r]，答案即为 max(pre[j+1] - min_s[j % k])。

算法分析

  • 核心：前缀和 + 模运算分类 + 贪心维护最小值。
  • 关键技巧：
    • 将前缀和按 位置 % k 分类，同余类内的前缀和才能组成长度为 k 的倍数的子数组。
    • 维护每个余数类下的最小前缀和，最大化子数组和。
    • 初始化时，min_s[k-1] = 0 表示空前缀和（对应索引 -1）。
  • 时间复杂度：O(n)，只需一次遍历。
  • 空间复杂度：O(k)，存储 k 种余数的最小前缀和。

代码实现（Python）

方法一：使用 accumulate 构建前缀和

from itertools import accumulate
from math import inf
from typing import List

class Solution:
    def maxSubarraySum(self, nums: List[int], k: int) -> int:
        # 计算前缀和数组，pre[i] 表示 nums 的前 i 个元素之和，初始加上 0 方便处理前缀和
        pre = list(accumulate(nums, initial=0))
        # 记录每种余数下对应的最小前缀和，初值为无穷大
        min_s = [inf] * k
        ans = -inf  # 初始化答案为负无穷
        for j, s in enumerate(pre):
            i = j % k  # 当前前缀和的下标对 k 取模，代表这一类余数
            # 更新答案，s - min_s[i] 表示以当前位置结尾的、长度可被 k 整除的子数组最大和
            ans = max(ans, s - min_s[i])
            # 维护每个余数对应的最小前缀和
            min_s[i] = min(min_s[i], s)
        return ans

方法二：手动维护前缀和

from math import inf
from typing import List

class Solution:
    def maxSubarraySum(self, nums: List[int], k: int) -> int:
        # 初始化每种余数下的最小前缀和数组，初值为正无穷大
        min_s = [inf] * k
        # 特殊处理，让初始余数为 -1（实际对应 k-1）的位置为0，代表前缀和起点
        min_s[-1] = s = 0
        ans = -inf  # 初始化最大和为负无穷
        for j, x in enumerate(nums):
            s += x  # 累加当前元素到前缀和
            i = j % k  # 当前下标对k取模，代表子数组长度模k的类型
            # 以当前位置结尾、长度可被k整除的子数组最大和
            ans = max(ans, s - min_s[i])
            # 更新当前模k类型下最小前缀和
            min_s[i] = min(min_s[i], s)
        return ans

代码实现（Go）

package main

import "math"

func maxSubarraySum(nums []int, k int) int64 {
    sum := make([]int, len(nums)+1)
    // calculate prefix sum
    for i, x := range nums {
        sum[i+1] = sum[i] + x
    }
    minSum := make([]int, k)
    for i := range minSum {
        minSum[i] = math.MaxInt64 / 2
    }
    ans := math.MinInt
    for j, s := range sum {
        i := j % k
        ans = max(ans, s-minSum[i])
        minSum[i] = min(minSum[i], s)
    }
    return int64(ans)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

代码实现（C++）

class Solution {
public:
    long long maxSubarraySum(vector<int>& nums, int k) {
        vector<long long> min_s(k, LLONG_MAX / 2);
        min_s.back() = 0;

        long long ans = LLONG_MIN;
        long long s = 0;
        for (int j = 0; j < nums.size(); ++j) {
            s += nums[j];
            int i = j % k;
            ans = max(ans, s - min_s[i]);
            min_s[i] = min(min_s[i], s);
        }
        return ans;
    }
};

测试用例

输入 输出 说明
nums = [1,2], k = 1 3 子数组 [1,2] 长度为 2，可被 1 整除，和为 3
nums = [-1,-2,-3,-4,-5], k = 4 -10 子数组 [-1,-2,-3,-4] 长度为 4，可被 4 整除，和为 -10
nums = [-5,1,2,-3,4], k = 2 4 子数组 [1,2,-3,4] 长度为 4，可被 2 整除，和为 4

总结与反思

  1. 本题是前缀和 + 模运算的经典应用，关键在于理解子数组长度能被 k 整除等价于起始位置和结束位置的前缀和索引模 k 同余。
  2. 通过维护每种余数下的最小前缀和，可以在 O(n) 时间内找到答案，避免了暴力枚举所有子数组的 O(n²) 复杂度。
  3. 初始化技巧：将 min_s[k-1] 设为 0，对应空前缀和（索引 -1），这样可以正确处理从数组开头开始的子数组。
  4. 注意处理负数情况，答案可能为负数，初始化时不能设为 0。