由于数据范围是2*10^5所以必然是遍历一次，子数组必定要用到前缀和，之前的题目中总是遇到的是子数组的和能不能被k整除，而这里不一样的是子数组的长度能不能被k整除，如果单纯的枚举长度必定超时，而看看题解得出的思路，我在做之前的题目中也有类似的。
首先，我们要想判断一个长度能不能被k整除，实际上就是判断 （j-i)%k==0 ，也就是说 j%k=i%k 同余定理，而求子数组的最大元素和，实际上就是求sum[j]-sum[i]，那么我们如何找这个符合条件的i呢，我们只需要让sum[i]尽可能的小，sum[j]尽可能的大，在满足这两个条件的情况下，实际上就是让我们求：sum[j]-sum[j%k(i)]的最大值sum[j]它是可以在枚举的过程中不断更新的，而我们需要确定的是j%k也就是i的最小值。
我们可以用一个最小值数组来保存每遇到一个j，它取模后的值（也就是i）的最小值
这样我们就能在枚举的过程中不断的更新sum[i]的最小值，从而求出子数组和的最大值。
下面是求与j同余的i的最小值的方法
int i =j%k;
minn[i]=min(minn[i],sum[j]);
下面是通过代码：
class Solution {
public:
long long sum[200005];
long long minn[200005];
long long maxSubarraySum(vector<int>& nums, int k) {
for(int i=0;i<k;i++)
{
minn[i]=LLONG_MAX/2;
}
minn[0]=0;
for(int i=0;i<nums.size();i++)
{
sum[i+1]=sum[i]+nums[i];
}
//我们要想判断一个长度能不能被k整除
//实际上就是判断 （j-i)%k==0
//也就是说 j%k=i%k 同余定理
//而求子数组的最大元素和
//实际上就是求sum[j]-sum[i]
//那么我们如何找这个符合条件的i呢
//我们可以在
//我们只需要让sum[i]尽可能的小
//sum[j]尽可能的大
//不断更新结果
long long ans=LLONG_MIN;
for(int j=1;j<=nums.size();j++)
{
int i=j%k;
ans=max(ans,sum[j]-minn[i]);
minn[i]=min(minn[i],sum[j]);
}
return ans;
}
};
要注意的是minn[i]初始化为LLONG_MAX/2，因为在减的过程中如果初始化为LLONG_MAX，那么相减的值可能是一个正数，而不是负数了，这样在 ans=max(ans,sum[j]-minn[i]);就会更新到错误的答案，我之前没有加出错了，所以必须加上。还有一点要注意如果j%k==0，也就是i=0，那么它初始化的最小值应该为0，也就是minn[0]=0;而不是LLONG_MAX/2;
时间复杂度O(n)。