力扣3381.长度可被K整除的子数组的最大元素和
力扣3381.长度可被K整除的子数组的最大元素和
题目
题目解析及思路
题目要求返回一段长度为K的倍数的最大子数组和
同余+前缀和
代码
class Solution {
public:
long long maxSubarraySum(vector<int>& nums, int k) {
int n = nums.size();
vector<long long> sum(n + 1);
for (int i = 0; i < n; i++) {
sum[i + 1] = sum[i] + nums[i];
}
//存每个余数的最小值
vector<long long> min_s(k, LLONG_MAX / 2);
long long ans = LLONG_MIN;
for (int j = 0; j < sum.size(); j++) {
//取j的余数
int i = j % k;
ans = max(ans, sum[j] - min_s[i]);
min_s[i] = min(min_s[i], sum[j]);
}
return ans;
}
};
原文地址：https://blog.csdn.net/Pisasama/article/details/144327355
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！