【C++前缀和】3026. 最大好子数组和|1816

本文涉及的基础知识点

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频

LeetCode3026. 最大好子数组和

给你一个长度为 n 的数组 nums 和一个 正 整数 k 。
如果 nums 的一个
子数组
中，第一个元素和最后一个元素 差的绝对值恰好 为 k ，我们称这个子数组为 好 的。换句话说，如果子数组 nums[i…j] 满足 |nums[i] - nums[j]| == k ，那么它是一个好子数组。
请你返回 nums 中 好 子数组的 最大 和，如果没有好子数组，返回 0 。
示例 1：
输入：nums = [1,2,3,4,5,6], k = 1
输出：11
解释：好子数组中第一个元素和最后一个元素的差的绝对值必须为 1 。好子数组有 [1,2] ，[2,3] ，[3,4] ，[4,5] 和 [5,6] 。最大子数组和为 11 ，对应的子数组为 [5,6] 。
示例 2：
输入：nums = [-1,3,2,4,5], k = 3
输出：11
解释：好子数组中第一个元素和最后一个元素的差的绝对值必须为 3 。好子数组有 [-1,3,2] 和 [2,4,5] 。最大子数组和为 11 ，对应的子数组为 [2,4,5] 。
示例 3：
输入：nums = [-1,-2,-3,-4], k = 2
输出：-6
解释：好子数组中第一个元素和最后一个元素的差的绝对值必须为 2 。好子数组有 [-1,-2,-3] 和 [-2,-3,-4] 。最大子数组和为 -6 ，对应的子数组为 [-1,-2,-3] 。
提示：
2 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
1 <= k <= 10⁹

前缀和

我们枚举非空子数组的最后一个元素下标j。nums[i,j] 必须非空，所以可以删除nums的前0个到j个元素。
preSum[j+1] - min(preSum[i]) && |nums[i]-nums[j]| == k 其i < j 。
即nums[j] = nums[i] $\pm$ k 。
如果多有个nums[j]相等 取和大的。
mValuePreSum 的key为：nums[i] value为：前i个元素的和。

代码

核心代码

class Solution {
public:
long long maximumSubarraySum(vector<int>& nums, int k) {
unordered_map<int, long long> mValuePreSum;
long long llRet = LLONG_MIN;
long long llSum = 0;
for (const auto& n : nums)
{
auto Do = [&](int pre)
{
if (!mValuePreSum.count(pre))
{
return;
}
llRet = max(llRet, llSum + n - mValuePreSum[pre]);
};
Do(n + k);
Do(n - k);
if ((!mValuePreSum.count(n)) || (mValuePreSum[n] > llSum))
{
mValuePreSum[n] = llSum;
}
llSum += n;
}
return (LLONG_MIN==llRet)?0:llRet;
}
};

单元测试

vector<int> nums;
int k;
TEST_METHOD(TestMethod11)
{
nums = { 1, 2, 3, 4, 5, 6 }, k = 1;
auto res = Solution().maximumSubarraySum(nums, k);
AssertEx(11LL, res);
}
TEST_METHOD(TestMethod12)
{
nums = { -1,3,2,4,5 }, k = 3;
auto res = Solution().maximumSubarraySum(nums, k);
AssertEx(11LL, res);
}
TEST_METHOD(TestMethod13)
{
nums = { -1,-2,-3,-4 }, k =2;
auto res = Solution().maximumSubarraySum(nums, k);
AssertEx(-6LL, res);
}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

原文地址：https://blog.csdn.net/he_zhidan/article/details/141858249

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！