【C++前后缀分解】1031. 两个非重叠子数组的最大和|1680
本文涉及知识点
C++前后缀分解
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
C++算法：滑动窗口总结
LeetCode1031. 两个非重叠子数组的最大和
给你一个整数数组 nums 和两个整数 firstLen 和 secondLen，请你找出并返回两个非重叠 子数组 中元素的最大和，长度分别为 firstLen 和 secondLen 。
长度为 firstLen 的子数组可以出现在长为 secondLen 的子数组之前或之后，但二者必须是不重叠的。
子数组是数组的一个 连续 部分。
示例 1：
输入：nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
输出：20
解释：子数组的一种选择中，[9] 长度为 1，[6,5] 长度为 2。
示例 2：
输入：nums = [3,8,1,3,2,1,8,9,0], firstLen = 3, secondLen = 2
输出：29
解释：子数组的一种选择中，[3,8,1] 长度为 3，[8,9] 长度为 2。
示例 3：
输入：nums = [2,1,5,6,0,9,5,0,3,8], firstLen = 4, secondLen = 3
输出：31
解释：子数组的一种选择中，[5,6,0,9] 长度为 4，[0,3,8] 长度为 3。
提示：
1 <= firstLen, secondLen <= 1000
2 <= firstLen + secondLen <= 1000
firstLen + secondLen <= nums.length <= 1000
0 <= nums[i] <= 1000
前后缀分解
n = nums.length
令Do(nums,firstLen,secondLen) 限度firstLen在secondLen之前的最大和。
max(Do(nums,firstLen,secondLen),Do(nums,secondLen,firstLen))就是本题的解。
Left[i] 记录nums长度为i的前缀中 长度为firstLen的子数组最大和，如果不存在其值为-1e7。
right[i]记录nums长度为i的后缀中，长度为secondLen的子数组最大和，，如果不存在其值为-1e7。
left[i]+right[n-i]的最大值就是Do的返回值。
注意： nums的转置数组的前缀就是nums的后缀。
代码
核心代码
class Solution {
public:
int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
m_iN = nums.size();
return max(Do(nums, firstLen, secondLen), Do(nums, secondLen, firstLen));
}
int Do(vector<int>& nums, int firstLen, int secondLen) {
auto left = MaxPreSum(nums, firstLen);
auto right = MaxPreSum(vector<int>(nums.rbegin(), nums.rend()), secondLen);
int ret = 0;
for (int i = 0; i <= m_iN; i++) {
ret = max(ret, left[i] + right[m_iN - i]);
}
return ret;
}
vector<int> MaxPreSum(const vector<int>& nums, int len) {
vector<int> preSum(m_iN+1);
partial_sum(nums.begin(), nums.end(), preSum.data() + 1);
vector<int> ret(m_iN+1, -1e7);
for (int i = len ; i <= m_iN; i++) {
ret[i] = preSum[i ] - preSum[i - len];
ret[i] = max(ret[i], ret[i - 1]);
}
return ret;
}
int m_iN;
};
单元测试
vector<int> nums;
int firstLen, secondLen;
TEST_METHOD(TestMethod11)
{
nums = { 0, 6, 5, 2, 2, 5, 1, 9, 4 }, firstLen = 1, secondLen = 2;
auto res = Solution().maxSumTwoNoOverlap(nums, firstLen, secondLen);
AssertEx(20, res);
}
TEST_METHOD(TestMethod12)
{
nums = { 3,8,1,3,2,1,8,9,0 }, firstLen = 3, secondLen = 2;
auto res = Solution().maxSumTwoNoOverlap(nums, firstLen, secondLen);
AssertEx(29, res);
}
TEST_METHOD(TestMethod13)
{
nums = { 2,1,5,6,0,9,5,0,3,8 }, firstLen = 4, secondLen = 3;
auto res = Solution().maxSumTwoNoOverlap(nums, firstLen, secondLen);
AssertEx(31, 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/142147583
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！