专栏首页算法修养LeetCode 1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target(动态规划)

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

题目

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

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

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

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];
}
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode Weekly Contest 30解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 【leetcode】高频题目整理_数组篇( High Frequency Problems, Array )

    截止至今LeetCode题目总量已经有1582题,估计将来每年平均增长300题左右,大部分人肯定是刷不完的,所以得有选择地刷LeetCode。

    嵌入式与Linux那些事
  • LeetCode笔记:Weekly Contest 201 比赛记录

    第一题看似有点复杂,但是终究是一道easy的题目,我们只需要注意例二中给出的情况,即在删除了bB之后,后面的A需要与上一个a进行比较,因此,这道题目就是一个比较...

    codename_cys
  • GitHub高星!互联网公司最常见的面试算法题大集合

    LeetCode是一个美国的在线编程网站,收集了各个大厂的笔试面试题,对找工作的毕业生和开发者来说,非常有价值。不过LeetCode上面的题目很多都是考察应聘者...

    新智元
  • LeetCode Weekly Contest 40解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 【论文推荐】最新6篇目标检测​(Object Detection)相关论文—物体链接、手机端、三维地图、航空图像、检测与姿态估计

    【导读】专知内容组整理了最近六篇目标检测(Object Detection)相关文章,为大家进行介绍,欢迎查看! 1. Object Detection in ...

    WZEARW
  • prometheus使用总结(2)

    建议使用第五步启动方式,找到配置文件加上--web.enable-lifecycle,此参数的意义在于我们修改了prometheus.yml后直接远程热加载即可...

    Bob hadoop
  • 39. 组合总和

    给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

    lucifer210
  • 卷积神经网络中PET/CT图像的纹理特征提取

    Author: Zongwei Zhou 周纵苇 Weibo: @MrGiovanni Email: zongweiz@asu.edu Please cit...

    用户1332428
  • 40. 组合总和 II

    给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

    lucifer210
  • 32类计算机与数学领域最为重要的算法

    导读: 奥地利符号计算研究所的Christoph Koutschan博士在自己的页面上发布了一篇文章,提到他做了一个调查,参与者大多数是计算机科学家,他请这些科...

    钱塘数据
  • LeetCode 动态规划 题目分类汇总

    A robot is located at the top-left corner of a m x n grid (marked 'Start' in the...

    Yano_nankai
  • Js算法与数据结构拾萃(1)

    算法是为了解决某些问题所提供的精确解法,数据结构是为了支撑算法提供的一种存储结构。

    一粒小麦
  • Flink 聚合性能优化 -- MiniBatch 分析

    Flink 1.9.0 SQL(Blink Planner) 性能优化中一项重要的改进就是升级了微批模型,即 MiniBatch(也称作MicroBatch或M...

    zhisheng
  • 贪心算法及Jump Game系列题详解

    贪心策略的选取将对贪心算法能否得到最优解起到了决定性的作用。最优子结构指的是,大问题分解成小问题时,使用拟定好的贪心策略一样能得到小问题的最优解。

    Steve Wang
  • POJ-2346 Lucky tickets(线性DP)

    Lucky tickets Time Limit: 1000MS Memory Limit: 65536K Total Submissions...

    ShenduCC
  • 198. 打家劫舍

    你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小...

    lucifer210
  • LeetCode Weekly Contest 37解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • python 分水岭算法的实现

    “”“ watershed.py-分水岭算法 该模块实现了分水岭算法,可将像素分配到标记的盆地中。 该算法使用优先级队列来保存像素,优先级队列的度量标准是像素值...

    用户7886150

扫码关注云+社区

领取腾讯云代金券