LeetCode 1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target(动态规划)

class Solution {
public:
    int dp[100005];
int sum[100005];
map<int, int> m;
int maxNonOverlapping(vector<int>& nums, int target) {

	sum[0] = nums[0];
	dp[0] = 0;
	if (nums[0] == target)
		dp[0] = 1;
	
	m[0] = -1;
    m[nums[0]] = 0;
	for (int i = 1; i < nums.size(); i++)
	{
		sum[i] = nums[i] + sum[i - 1];
		int left = sum[i] - target;
		if (m.find(left) == m.end())
		{
			dp[i] = dp[i - 1];
		}
		else
		{
			int pos = m[left];
			dp[i] = max(dp[i - 1], (pos == -1 ? 0 : dp[pos]) + 1);
		}

		m[sum[i]] = i;
	}

	return dp[nums.size() - 1];
}
};