Medium

题目描述

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

返回 nums 的一个子数组的最大和，使得该子数组的长度可以被 k 整除。

示例 1：

输入：nums = [1,2], k = 1
输出：3
解释：
子数组 [1, 2] 的和为 3，长度为 2，可以被 1 整除。

示例 2：

输入：nums = [-1,-2,-3,-4,-5], k = 4
输出：-10
解释：
最大和子数组是 [-1, -2, -3, -4]，长度为 4，可以被 4 整除。

示例 3：

输入：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

提示：

  • 维护每个可能的 index % k 处结束的最小前缀和。

解题思路

这个问题的核心在于找到长度可被 k 整除的子数组中和最大的一个。我们可以使用前缀和的思想来解决。

核心思路： 要使子数组 nums[i...j] 的长度可被 k 整除，需要满足 (j - i + 1) % k == 0，即 j % k == (i - 1) % k。

我们可以计算前缀和，然后对于每个位置 j，我们需要找到最小的前缀和 prefix[i-1]，使得 (i-1) % k == j % k。这样 prefix[j] - prefix[i-1] 就是以 j 结尾、长度可被 k 整除的子数组的最大和。

算法步骤：

  1. 维护一个数组 minPrefix，其中 minPrefix[r] 表示所有满足 index % k == r 的位置中的最小前缀和
  2. 遍历数组，计算前缀和
  3. 对于每个位置 j，如果 j >= k-1（确保存在长度至少为 k 的子数组），则用当前前缀和减去对应的最小前缀和来更新答案
  4. 更新 minPrefix 数组

这种方法的时间复杂度是 O(n)，空间复杂度是 O(k)，是最优解法。

代码实现

class Solution {
public:
    long long maxSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long long> minPrefix(k, LLONG_MAX);
        minPrefix[0] = 0;
        
        long long prefixSum = 0;
        long long maxSum = LLONG_MIN;
        
        for (int i = 0; i < n; i++) {
            prefixSum += nums[i];
            
            if (i >= k - 1) {
                int remainder = (i + 1) % k;
                if (minPrefix[remainder] != LLONG_MAX) {
                    maxSum = max(maxSum, prefixSum - minPrefix[remainder]);
                }
            }
            
            int currentRemainder = (i + 1) % k;
            minPrefix[currentRemainder] = min(minPrefix[currentRemainder], prefixSum);
        }
        
        return maxSum;
    }
};

class Solution:
    def maxSubarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        min_prefix = [float('inf')] * k
        min_prefix[0] = 0
        
        prefix_sum = 0
        max_sum = float('-inf')
        
        for i in range(n):
            prefix_sum += nums[i]
            
            if i >= k - 1:
                remainder = (i + 1) % k
                if min_prefix[remainder] != float('inf'):
                    max_sum = max(max_sum, prefix_sum - min_prefix[remainder])
            
            current_remainder = (i + 1) % k
            min_prefix[current_remainder] = min(min_prefix[current_remainder], prefix_sum)
        
        return max_sum

public class Solution {
    public long MaxSubarraySum(int[] nums, int k) {
        int n = nums.Length;
        long[] minPrefix = new long[k];
        for (int i = 0; i < k; i++) {
            minPrefix[i] = long.MaxValue;
        }
        minPrefix[0] = 0;
        
        long prefixSum = 0;
        long maxSum = long.MinValue;
        
        for (int i = 0; i < n; i++) {
            prefixSum += nums[i];
            
            if (i >= k - 1) {
                int remainder = (i + 1) % k;
                if (minPrefix[remainder] != long.MaxValue) {
                    maxSum = Math.Max(maxSum, prefixSum - minPrefix[remainder]);
                }
            }
            
            int currentRemainder = (i + 1) % k;
            minPrefix[currentRemainder] = Math.Min(minPrefix[currentRemainder], prefixSum);
        }
        
        return maxSum;
    }
}

var maxSubarraySum = function(nums, k) {
    const n = nums.length;
    const minPrefix = new Array(k).fill(Number.MAX_SAFE_INTEGER);
    minPrefix[0] = 0;
    
    let prefixSum = 0;
    let maxSum = Number.MIN_SAFE_INTEGER;
    
    for (let i = 0; i < n; i++) {
        prefixSum += nums[i];
        
        if (i >= k - 1) {
            const remainder = (i + 1) % k;
            if (minPrefix[remainder] !== Number.MAX_SAFE_INTEGER) {
                maxSum = Math.max(maxSum, prefixSum - minPrefix[remainder]);
            }
        }
        
        const currentRemainder = (i + 1) % k;
        minPrefix[currentRemainder] = Math.min(minPrefix[currentRemainder], prefixSum);
    }
    
    return maxSum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需要遍历数组一次，每次操作都是常数时间
空间复杂度O(k)需要额外的数组来存储每个余数对应的最小前缀和

相关题目