【动态规划】【前缀和】【和式变换】100216. K 个不相交子数组的最大能量值

本文涉及知识点

动态规划汇总

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 public: long long maximumStrength(vector m_c = nums.size(); vector vector 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 maxPre = -1E14,llMax = -1E14,llSum=0; for (int j = 1; 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 maxPre = (long long)-1E14, llMax = -1E14, llSum = 0; for (int j = 1; 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; }; assert(t1 == t2); } template if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i