本文涉及知识点

C++动态规划

LeetCode3196. 最大化子数组的总成本

给你一个长度为 n 的整数数组 nums。
子数组 nums[l…r]（其中 0 <= l <= r < n）的 成本 定义为：
cost(l, r) = nums[l] - nums[l + 1] + … + nums[r] * (−1)r − l
你的任务是将 nums 分割成若干子数组，使得所有子数组的成本之和 最大化，并确保每个元素 正好 属于一个子数组。
具体来说，如果 nums 被分割成 k 个子数组，且分割点为索引 i1, i2, …, ik − 1（其中 0 <= i1 < i2 < … < ik - 1 < n - 1），则总成本为：
cost(0, i1) + cost(i1 + 1, i2) + … + cost(ik − 1 + 1, n − 1)
返回在最优分割方式下的子数组成本之和的最大值。
注意：如果 nums 没有被分割，即 k = 1，则总成本即为 cost(0, n - 1)。
示例 1：
输入： nums = [1,-2,3,4]
输出： 10
解释：
一种总成本最大化的方法是将 [1, -2, 3, 4] 分割成子数组 [1, -2, 3] 和 [4]。总成本为 (1 + 2 + 3) + 4 = 10。
示例 2：
输入： nums = [1,-1,1,-1]
输出： 4
解释：
一种总成本最大化的方法是将 [1, -1, 1, -1] 分割成子数组 [1, -1] 和 [1, -1]。总成本为 (1 + 1) + (1 + 1) = 4。
示例 3：
输入： nums = [0]
输出： 0
解释：
无法进一步分割数组，因此答案为 0。
示例 4：
输入： nums = [1,-1]
输出： 2
解释：
选择整个数组，总成本为 1 + 1 = 2，这是可能的最大成本。
提示：
1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹

动态规划

只需要考虑长度为1或2的子数组，长度大于3的子数组，将前两个元素单独处理，结果一样。

动态规划的状态表示

dp[i] 表示划分完前i个元素的最大成本和。空间复杂度：O(n)。

动态规划的转移方程

MaxSelf(dp[i+1],dp[i]+nums[i]);
MaxSelf(dp[i+2],dp[i]+nums[i]-nums[i+1]);

动态规划的初始值

dp[0]=0 ，其它全为LLONG_MIN/10。

动态规划的填报顺序

i 从 0到 n-1

动态规划的返回值

dp.back()

代码

核心代码

class Solution {
		public:
			long long maximumTotalCost(vector<int>& nums) {
				const int & N = nums.size();
				vector<long long> dp(N + 1, LLONG_MIN / 10);
				dp[0] = 0;
				for (int i = 0; i + 2 <= N; i++) {
					dp[i + 1]= max(dp[i + 1], dp[i] + nums[i]);
					dp[i + 2] = max(dp[i + 2], dp[i] + nums[i]-nums[i+1]);
				}
				dp[N] = max(dp[N], dp[N - 1] + nums.back());
				return dp.back();
			}
		};

单元测试

vector<int> nums;
		TEST_METHOD(TestMethod11)
		{
			nums = { 1,-2,3,4 };
			auto res = Solution().maximumTotalCost(nums);
			AssertEx(10LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 1,-1,1,-1 };
			auto res = Solution().maximumTotalCost(nums);
			AssertEx(4LL, res);
		}
		TEST_METHOD(TestMethod13)
		{
			nums = { 0 };
			auto res = Solution().maximumTotalCost(nums);
			AssertEx(0LL, res);
		}
		TEST_METHOD(TestMethod14)
		{
			nums = { 1,-1 };
			auto res = Solution().maximumTotalCost(nums);
			AssertEx(2LL, res);
		}