本文涉及知识点
动态规划汇总
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
LeetCode 100216. K 个不相交子数组的最大能量值
给你一个长度为 n 下标从 0 开始的整数数组 nums 和一个 正奇数 整数 k 。
x 个子数组的能量值定义为 strength = sum[1] * x - sum[2] * (x - 1) + sum[3] * (x - 2) - sum[4] * (x - 3) + … + sum[x] * 1 ，其中 sum[i] 是第 i 个子数组的和。更正式的，能量值是满足 1 <= i <= x 的所有 i 对应的 (-1)i+1 * sum[i] * (x - i + 1) 之和。
你需要在 nums 中选择 k 个 不相交子数组 ，使得 能量值最大 。
请你返回可以得到的 最大能量值 。
注意，选出来的所有子数组 不 需要覆盖整个数组。
示例 1：
输入：nums = [1,2,3,-1,2], k = 3
输出：22
解释：选择 3 个子数组的最好方式是选择：nums[0…2] ，nums[3…3] 和 nums[4…4] 。能量值为 (1 + 2 + 3) * 3 - (-1) * 2 + 2 * 1 = 22 。
示例 2：
输入：nums = [12,-2,-2,-2,-2], k = 5
输出：64
解释：唯一一种选 5 个不相交子数组的方案是：nums[0…0] ，nums[1…1] ，nums[2…2] ，nums[3…3] 和 nums[4…4] 。能量值为 12 * 5 - (-2) * 4 + (-2) * 3 - (-2) * 2 + (-2) * 1 = 64 。
示例 3：
输入：nums = [-1,-2,-3], k = 1
输出：-1
解释：选择 1 个子数组的最优方案是：nums[0…0] 。能量值为 -1 。
提示：
1 <= n <= 104
-109 <= nums[i] <= 109
1 <= k <= n
1 <= n * k <= 106
k 是奇数。
动态规划
动态规划的状态表示
iK
∈
\in
∈[0,k)
pre[j]表示从nums[0…j)选择前iK-1个子数组组成的表达式的最大和。最后一个子数组以nums[j-1]结尾。
dp[j]表示从nums[0…j)选择前iK个子数组组成的表达式的最大和。最后一个子数组以nums[j-1]结尾。
利用和式变换简化动态规划的转移方程
假定第iK个子数组为nums[i…j]，maxK1[j] =
M
a
x
x
:
0
j
\Large Max_{x:0}^{j}
Maxx:0jpre[j]。
如果iK是偶数：
d
p
[
j
]
=
M
a
x
i
:
1
j
(
M
a
x
m
a
x
K
1
[
i
−
1
]
+
S
u
m
[
0...
j
]
−
S
u
m
[
0...
i
−
1
]
)
dp[j] = Max_{i:1}^{j} (MaxmaxK1[i-1] + Sum[0...j]- Sum[0...i-1])
dp[j]=Maxi:1j(MaxmaxK1[i−1]+Sum[0...j]−Sum[0...i−1])
→
M
a
x
i
:
1
j
(
M
a
x
m
a
x
K
1
[
i
−
1
]
−
S
u
m
[
0...
i
−
1
]
)
+
S
u
m
[
0...
j
]
\rightarrow Max_{i:1}^{j} (MaxmaxK1[i-1] - Sum[0...i-1])+ Sum[0...j]
→Maxi:1j(MaxmaxK1[i−1]−Sum[0...i−1])+Sum[0...j]
令
m
a
x
1
(
j
)
=
M
a
x
i
:
1
j
(
M
a
x
m
a
x
K
1
[
i
−
1
]
−
S
u
m
[
0...
i
−
1
]
)
令max1(j) = Max_{i:1}^{j} (MaxmaxK1[i-1] - Sum[0...i-1])
令max1(j)=Maxi:1j(MaxmaxK1[i−1]−Sum[0...i−1])
一个式子包括两个式子，分别用前缀和优化性质。
显然max1(j+1) = max( max1(j),MaxmaxK1[j] - Sum[0…j])
这是前缀和的基础。
如果iK是偶数：
d
p
[
j
]
=
M
a
x
i
:
1
j
(
M
a
x
m
a
x
K
1
[
i
−
1
]
+
S
u
m
[
0...
i
−
1
]
)
−
S
u
m
[
0...
j
]
dp[j] = \Large Max_{i:1}^{j} (MaxmaxK1[i-1] + Sum[0...i-1])- Sum[0...j]
dp[j]=Maxi:1j(MaxmaxK1[i−1]+Sum[0...i−1])−Sum[0...j]
动态规划的初始值
pre全部为0。
动态规划的填表顺序
ik从0到iK-1,j从1到n。
特例
由于 k <= n，故一定能拆分成k组，前iK组的和一定大于等于 -1013 ,我们用-1014表示非法。
代码
核心代码
class Solution {
public:
long long maximumStrength(vector<int>& nums, int k) {
m_c = nums.size();
vector<long long> pre(m_c+1);
for (int iK = 0; iK < k; iK++)
{
vector<long long> dp(m_c + 1, -1E14);
if (1 & iK)
{
Odd(dp, pre, nums,k-iK);
}
else
{
Even(dp, pre, nums, k - iK);
}
pre.swap(dp);
}
return *std::max_element(pre.begin(), pre.end());
}
void Odd(vector<long long>& dp, const vector<long long>& pre,const vector<int>& nums,const int x )
{//奇数
long long maxPre = -1E14,llMax = -1E14,llSum=0;
for (int j = 1; j <= m_c ; j++)
{//假定第iK个子数组是nums[i,j]，则最大值为：maxPre - sum[0...j] + sum[0...i)，llMax=第一项和第三项合并
maxPre = max(maxPre, pre[j-1]);
llMax = max(llMax, maxPre + llSum);//第iK个子数组，以nums[j]开头
llSum += (long long)nums[j-1]*x;
dp[j] = llMax - llSum;
}
}
void Even(vector<long long>& dp, const vector<long long>& pre, const vector<int>& nums, const int x)
{//偶数
long long maxPre = (long long)-1E14, llMax = -1E14, llSum = 0;
for (int j = 1; j <= m_c; j++)
{//假定第iK个子数组是nums[i,j]，则最大值为：maxPre + sum[0...j] - sum[0...i)，llMax=第一项和第三项合并
maxPre = max(maxPre, pre[j-1]);
llMax = max(llMax, maxPre - llSum);//第iK个子数组，以nums[j]开头
llSum += (long long)nums[j - 1] * x;
dp[j] = llMax + llSum;
}
}
int m_c;
};
测试用例
template<class T, class T2>
void Assert(const T& t1, const T2& 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()
{
vect
or<int> nums;
int k;
{
Solution sln;
nums = { -100000000, -10000000, 123, 234 }, k = 3;
auto res = sln.maximumStrength(nums, k);
Assert(-30000012, res);
}
{
Solution sln;
nums = { 1,2,3,-1,2 }, k = 3;
auto res = sln.maximumStrength(nums, k);
Assert(22, res);
}
{
Solution sln;
nums = { 12,-2,-2,-2,-2 }, k = 5;
auto res = sln.maximumStrength(nums, k);
Assert(64, res);
}
{
Solution sln;
nums = { -1,-2,-3 }, k = 1;
auto res = sln.maximumStrength(nums, k);
Assert(-1, res);
}
}
优化
pre[j]表示从nums[0…j)选择前iK-1个子数组组成的表达式的最大和。最后一个子数组以nums[x]结尾,x ∈ \in ∈[0,j)。
class Solution {
public:
long long maximumStrength(vector<int>& nums, int k) {
m_c = nums.size();
vector<long long> pre(m_c + 1);
for (int iK = 0; iK < k; iK++)
{
vector<long long> dp(m_c + 1, -1E14);
long long maxAdd = -1E14, maxSub = -1E14,maxPre = -1E14;
long long llSum = 0;
for (int j = 1; j <= m_c; j++)
{
maxPre = max(maxPre, pre[j-1]);
maxAdd = max(maxAdd, maxPre - llSum);
maxSub = max(maxSub, maxPre + llSum);
llSum += nums[j - 1]*(long long) ( k - iK );
dp[j] = (iK & 1) ? (maxSub - llSum) : (maxAdd + llSum);
}
pre.swap(dp);
}
return *std::max_element(pre.begin(), pre.end());
}
int m_c;
};
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。文章来源：https://www.toymoban.com/news/detail-838813.html
文章来源地址https://www.toymoban.com/news/detail-838813.html
到了这里，关于【动态规划】【前缀和】【和式变换】100216. K 个不相交子数组的最大能量值的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
