作者推荐
本文涉及知识点
滚动向量 离线查询
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<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) { m_c = nums.size(); vector<int> vPreSum = { 0 }; for (const auto& n : nums) { vPreSum.emplace_back(vPreSum.back() + n); } vector<int> pre(m_c + 1,-1); vector<vector<int>> vPreLen(4, vector<int>(m_c + 1)); pre[0] = 0; for (int i = 1; i <= 3; i++) { int iMax = 0,iMaxIndex=-1; vector<int> dp(m_c + 1,-1); 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<int> vRet(3); 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<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { 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> nums; int k; { Solution sln; nums = { 1, 2, 1, 2, 6, 7, 5, 1 }, k = 2; auto res = sln.maxSumOfThreeSubarrays(nums, k); Assert(vector<int>{0, 3, 5}, res); } { Solution sln; nums = { 1,2,1,2,1,2,1,2,1 }, k = 2; auto res = sln.maxSumOfThreeSubarrays(nums, k); Assert(vector<int>{0, 2, 4}, res); } { Solution sln; nums = { 7,13,20,19,19,2,10,1,1,19 }, k = 3; auto res = sln.maxSumOfThreeSubarrays(nums, k); Assert(vector<int>{1,4,7}, res); } { Solution sln; nums.assign(20000,1<<16-1), k = 20000/3; auto res = sln.maxSumOfThreeSubarrays(nums, k); Assert(vector<int>{0, 6666, 13332}, res); } }
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<int,vector> mRightSumIndex;
for (int i = 1; i + k - 1 < nums.size(); i++)
{
vKSums.push_back(vKSums[i - 1] + nums[i + k - 1] - nums[i - 1]);
if (i >= k*2 )
{
mRightSumIndex[vKSums[i]].push_back(i);
}
}
vector ret = { 0, k, mRightSumIndex.rbegin()->second[0] };
int iLeftMax = vKSums[0];
int iLeftIndex = 0;
int iMax = vKSums[ret[0]] + vKSums[ret[1]] + vKSums[ret[2]];
for (int i = k; i + k < vKSums.size(); i++)
{
if (iLeftMax + vKSums[i] + mRightSumIndex.rbegin()->first > iMax)
{
ret = { iLeftIndex, i, mRightSumIndex.rbegin()->second[0] };
iMax = vKSums[ret[0]] + vKSums[ret[1]] + vKSums[ret[2]];
}
if (vKSums[i-k+1] > iLeftMax)
{
iLeftMax = vKSums[i - k + 1];
iLeftIndex = i - k + 1;
}
auto & v = mRightSumIndex[vKSums[i + k]];
v.erase(v.begin());
if (v.empty())
{
mRightSumIndex.erase(mRightSumIndex.find(vKSums[i + k]));
}
}
return ret;
}
};
