本文涉及知识点

C++动态规划

LeetCode2786. 访问数组中的位置使分数最大

给你一个下标从 0 开始的整数数组 nums 和一个正整数 x 。
你 一开始 在数组的位置 0 处，你可以按照下述规则访问数组中的其他位置：
如果你当前在位置 i ，那么你可以移动到满足 i < j 的 任意 位置 j 。
对于你访问的位置 i ，你可以获得分数 nums[i] 。
如果你从位置 i 移动到位置 j 且 nums[i] 和 nums[j] 的 奇偶性 不同，那么你将失去分数 x 。
请你返回你能得到的 最大 得分之和。
注意 ，你一开始的分数为 nums[0] 。
示例 1：
输入：nums = [2,3,6,1,9,2], x = 5
输出：13
解释：我们可以按顺序访问数组中的位置：0 -> 2 -> 3 -> 4 。
对应位置的值为 2 ，6 ，1 和 9 。因为 6 和 1 的奇偶性不同，所以下标从 2 -> 3 让你失去 x = 5 分。
总得分为：2 + 6 + 1 + 9 - 5 = 13 。
示例 2：
输入：nums = [2,4,6,8], x = 3
输出：20
解释：数组中的所有元素奇偶性都一样，所以我们可以将每个元素都访问一次，而且不会失去任何分数。
总得分为：2 + 4 + 6 + 8 = 20 。
提示：
2 <= nums.length <= 10⁵
1 <= nums[i], x <= 10⁶

动态规划

动态规划的状态表示

dp[i][j] 处理完nums[0…i]的最大分数，j为1表示最后选择的数组是奇数，0是偶数。空间复杂度：O(n)

动态规划的转移方程

dp[i] = dp[i-1]不选择nums[i]
j1 =nums[i]%2
MaxSelf(dp[i][j1 ] ,dp[i-1][j] + nums[i] - ((j1!=j)?x:0) );
单个状态转移的时间复杂度：O(1)，总时间复杂度：O(n）

动态规划的填表顺序

枚举后序状态，i从1到n-1,j从0到1。

动态规划的初始值

dp[0][nums[0]%2] = nums[0] 其它全LLONG_MIN/10。

动态规划的返回值

dp.back()的最大值。

代码

核心代码

class Solution {
		public:
			long long maxScore(vector<int>& nums, int x) {
				const int N = nums.size();
				vector<vector<long long>> dp(N , vector<long long>(2,LLONG_MIN/2));
				dp[0][nums[0] % 2] = nums[0];
				for (int i = 1; i < N ; i++) {
					dp[i] =dp[i-1];
					const int j1 = nums[i] % 2;
					for (int j = 0; j < 2; j++) {	
						const long long sign = (j == j1) ? 0 : 1;
						dp[i][j1] = max(dp[i][j1],dp[i-1][j] + nums[i] - x *sign);
					}
				}
				return *max_element(dp.back().begin(), dp.back().end());
			}
		};

单元测试

vector<int> nums;
		int x;
		TEST_METHOD(TestMethod11)
		{
			nums = { 2, 3, 6, 1, 9,2 }, x = 5;
			auto res = Solution().maxScore(nums, x);
			AssertEx(13LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 2,4,6,8 }, x = 3;
			auto res = Solution().maxScore(nums, x);
			AssertEx(20LL, res);
		}