作者推荐
【动态规划】【数学】【C++算法】18赛车
本文涉及的基础知识点
动态规划 滚动向量 离线查询
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
LeetCode689. 三个无重叠子数组的最大和
给你一个整数数组 nums 和一个整数 k ，找出三个长度为 k 、互不重叠、且全部数字和（3 * k 项）最大的子数组，并返回这三个子数组。 以下标的数组形式返回结果，数组中的每一项分别指示每个子数组的起始位置（下标从 0 开始）。如果有多个结果，返回字典序最小的一个。 示例 1： 输入：nums = [1,2,1,2,6,7,5,1], k = 2 输出：[0,3,5] 解释：子数组 [1, 2], [2, 6], [7, 5] 对应的起始下标为 [0, 3, 5]。 也可以取 [2, 1], 但是结果 [1, 3, 5] 在字典序上更大。 示例 2： 输入：nums = [1,2,1,2,1,2,1,2,1], k = 2 输出：[0,2,4] 提示： 1 <= nums.length <= 2 * 104 1 <= nums[i] < 216 1 <= k <= floor(nums.length / 3)
动态规划
空间复杂度 O(n) 时间复杂度 O(n)· 动态规划的状态表示 pre[j]记录前j个数字中，i-1组的最大和。dp[j]记录前j个数字中,i组的最大和。-1表示非法值。i=1时,pre[0]=0是合法值。 动态规划的转移方程: dp[j+k] = Sum[j,j+k) + Max
[
0
,
j
]
k
\Large^k_{[0,j]}
[0,j]k(pre[k]) 。可以用前缀和离线查询。 动态规划的填表顺序 i从1到3,j从0到j+k <= m_c。 动态规划的范围值 pre的最大值。 vPreLen[i][j] 记录 nums[0,j) 分为i组和最大时：i-1组的j。
代码
核心代码
class Solution {
public:
vector
m_c = nums.size();
vector
for (const auto& n : nums)
{
vPreSum.emplace_back(vPreSum.back() + n);
}
vector
vector
pre[0] = 0;
for (int i = 1; i <= 3; i++)
{
int iMax = 0,iMaxIndex=-1;
vector
for (int j = 0; j + k <= m_c; j++)
{
if (pre[j] > iMax)
{
iMax = pre[j];
iMaxIndex = j;
}
if (iMax >= 0)
{
dp[j + k] = iMax + (vPreSum[j + k] - vPreSum[j]);
vPreLen[i][j+k] = iMaxIndex;
}
}
pre.swap(dp);
}
int len = std::max_element(pre.begin(), pre.end())- pre.begin();
vector
vRet[2] = len - k;
int len2 = vPreLen[3][len];
vRet[1] = len2 - k;
int len1 = vPreLen[2][len2];
vRet[0] = len1 - k;
return vRet;
}
int m_c;
};
测试用例
template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
template
void Assert(const vector
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}
int main()
{
vector
int k;
{
Solution sln;
nums = { 1, 2, 1, 2, 6, 7, 5, 1 }, k = 2;
auto res = sln.maxSumOfThreeSubarrays(nums, k);
Assert(vector
}
{
Solution sln;
nums = { 1,2,1,2,1,2,1,2,1 }, k = 2;
auto res = sln.maxSumOfThreeSubarrays(nums, k);
Assert(vector
}
{
Solution sln;
nums = { 7,13,20,19,19,2,10,1,1,19 }, k = 3;
auto res = sln.maxSumOfThreeSubarrays(nums, k);
Assert(vector
}
{
Solution sln;
nums.assign(20000,1<<16-1), k = 20000/3;
auto res = sln.maxSumOfThreeSubarrays(nums, k);
Assert(vector
}
}
2023年1月3号
class Solution { public: vector maxSumOfThreeSubarrays(vector& nums, int k) { vector vKSums; vKSums.push_back(std::accumulate(nums.begin(), nums.begin() + k, 0)); std::map
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程 https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙，那算法就是他的是睛
测试环境
操作系统：win7 开发环境： VS2019 C++17 或者 操作系统：win10 开发环境： VS2022 **C+
+17** 如无特殊说明，本算法用**C++**实现。
文章来源
发表评论