本文涉及的基础知识点

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
C++动态规划

C++贪心

LeetCode1546. 和为目标值且不重叠的非空子数组的最大数目

难度分：1855
给你一个数组 nums 和一个整数 target 。
请你返回 非空不重叠 子数组的最大数目，且每个子数组中数字和都为 target 。
示例 1：
输入：nums = [1,1,1,1,1], target = 2
输出：2
解释：总共有 2 个不重叠子数组（加粗数字表示） [1,1,1,1,1] ，它们的和为目标值 2 。
示例 2：
输入：nums = [-1,3,5,1,4,2,-9], target = 6
输出：2
解释：总共有 3 个子数组和为 6 。
([5,1], [4,2], [3,5,1,4,2,-9]) 但只有前 2 个是不重叠的。
示例 3：
输入：nums = [-2,6,6,3,5,4,1,2,8], target = 10
输出：3
示例 4：
输入：nums = [0,0,0], target = 0
输出：3
提示：
1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴
0 <= target <= 10⁶

贪心+前缀和

n = nums.size()
如果nums[i1…j]和nums[i2…j]的和都为target，且i1 < i2。如果存在最优方案包括nums[i1…j]，则替换成nums[i2…j]，仍然是最优解。故只需要考虑i2。
令dp[i]是nums前i个元素的最大数目,dp[n]就是本题的解。
由于数组非空，即子数组nums[i…j]，符合i <=j。即：preSum[j+1] - preSum[i] = target。
mValueIndex记录 preSum[i] 对应的下标，如果存在多个，以下标大的为准。
如果mValueIndex包括preSum[j+1] - target，且对应的值为i3，则dp[j] = dp[i3-1]+1。否则dp[j]=0。
注意：dp[i] = max(dp[i],dp[i-1])

动态规划+贪心+前缀和（题解2024年10月11）

如果nums[0…i]中，方案一能找到n1个子数组，方案二能找到n2个子数组。n1 < n2，则方案一一定不是最优解，将nums[0…i]中的子数组替换成方案二更短。

动态规划的状态表示

dp[i]表示nums长度为i的前缀最多子数组数量。空间复杂度：O(n)。

动态规划的转移方程

如果所有子数组不包括nums[i-1]，则dp[i] = dp[i-1]。
如果存在preSum[i] - preSum[j] = target，则dp[i] = dp[j]+1。如果有多个j，取最大。mPre[perSum[i]]=i，方便查找j。
单个状态的时间复杂度：O(1)。总时间复杂度：O(n)。

动态规划的填报顺序

i从1到n

动态规划初始值

dp全部为0。

动态规划的返回值

dp.back()

代码

核心代码

class Solution {
		public:
			int maxNonOverlapping(vector<int>& nums, int target) {
				vector<int> preSum(1);
				for (const auto& n : nums) {
					preSum.emplace_back(n + preSum.back());
				}
				unordered_map<int, int> mValueIndex;
				vector<int> dp(nums.size());
				for (int i = 0; i < nums.size(); i++) {
					mValueIndex[preSum[i]] = i;
					const int que = preSum[i + 1] - target;
					if (mValueIndex.count(que)) {
						auto tmp = mValueIndex[que] - 1;
						dp[i] = (tmp >=0 ? dp[tmp] : 0 ) + 1;
					}
					if (i > 0) {
						dp[i] = max(dp[i], dp[i - 1]);
					}
				}
				return dp.back();
			}
		};

单元测试

vector<int> nums;
		int target;
		TEST_METHOD(TestMethod11)
		{
			nums = { 1, 1, 1, 1, 1 }, target = 2;
			auto res = Solution().maxNonOverlapping(nums, target);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { -1, 3, 5, 1, 4, 2, -9 }, target = 6;
			auto res = Solution().maxNonOverlapping(nums, target);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod13)
		{
			nums = { -2,6,6,3,5,4,1,2,8 }, target = 10;
			auto res = Solution().maxNonOverlapping(nums, target);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod14)
		{
			nums = { 0,0,0 }, target = 0;
			auto res = Solution().maxNonOverlapping(nums, target);
			AssertEx(3, res);
		}