小工具知识网

当前位置: 首页 > 行业知识 > 【动态规划】【前缀和】【和式变换】100216. K 个不相交子数组的最大能量值

行业知识

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

2026-11-16 10:16:48 来源:互联网转载

本文涉及知识点

动���规划汇总

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(vectorm_c = nums.size();vectorvectorOdd(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);}templateif (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i

上一篇:电脑怎么查域名

下一篇:服务器怎么看存储阵列?