本文涉及知识点

C++动态规划

LeetCode1043. 分隔数组以得到最大和

给你一个整数数组 arr，请你将该数组分隔为长度 最多 为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。
返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。
示例 1：
输入：arr = [1,15,7,9,2,5,10], k = 3
输出：84
解释：数组变为 [15,15,15,9,10,10,10]
示例 2：
输入：arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
输出：83
示例 3：
输入：arr = [1], k = 1
输出：1
提示：
1 <= arr.length <= 500
0 <= arr[i] <= 10⁹
1 <= k <= arr.length

动态规划

vMax[i][j] 表示 nums[i…j]的最大值。

动态规划的状态表示

dp[i]表示nums[i]的前i个元素划分后的最大值。 空间复杂度：O(n)

动态规划的填表顺序

枚举前置状态，i = 0 To n-1 j = i to n-1

动态规划的转移方程

MaxSelf(dp[j+1],dp[i]+ vMax[i][j]*(j-i+1))
单个状态转移的时间复杂度：O(k),总时间复杂度：O(nk)

动态规划的初始值

dp[0]全为0。

动态规划的返回值

dp.back()

代码

核心代码

class Solution {
		public:
			int maxSumAfterPartitioning(vector<int>& arr, int k) {
				const int N = arr.size();
				vector<vector<int>> vMax(N, vector<int>(N));
				for (int i = 0; i < N; i++) {
					vMax[i][i] = arr[i];
					for (int j = i + 1; j < min(i + k,N); j++) {
						vMax[i][j] = max(vMax[i][j - 1], arr[j]);
					}
				}
				vector<int> dp(N+1, 0);
				for (int i = 0; i < N; i++) {
					for (int j = i ; j < min(i + k, N); j++) {
						dp[j + 1] = max(dp[j + 1], dp[i] + vMax[i][j] * (j - i + 1));
					}
				}
				return dp.back();
			}
		};

单元测试

vector<int> arr;
		int k;
		TEST_METHOD(TestMethod11)
		{
			arr = { 1, 15, 7, 9, 2, 5, 10 }, k = 3;
			auto res = Solution().maxSumAfterPartitioning(arr, k);
			AssertEx(84, res);
		}
		TEST_METHOD(TestMethod12)
		{
			arr = { 1,4,1,5,7,3,6,1,9,9,3 }, k = 4;
			auto res = Solution().maxSumAfterPartitioning(arr, k);
			AssertEx(83, res);
		}
		TEST_METHOD(TestMethod13)
		{
			arr = { 1 }, k = 1;
			auto res = Solution().maxSumAfterPartitioning(arr, k);
			AssertEx(1, res);
		}