前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target(动态规划)

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

作者头像
ShenduCC
发布2020-08-14 09:54:48
3750
发布2020-08-14 09:54:48
举报
文章被收录于专栏:算法修养

题目

题意:在一个数组中,找到最多的不相交的子序列,每个子序列的和等于target。

题解:动态规划 dp[i]表示从0到i的子数组的答案。维护前缀数组sums[],我们维护一个记录前缀和的map,map[x]表示前缀和是x距离当前i最近的下标。

那么状态转移方程就是dp[i] = max(dp[i-1], dp[map[sums[i]-target]]+1)

代码语言:javascript
复制
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];
}
};
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-08-13 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档