最大子段和(分治法+动态规划法)

求最大子段和

此类问题通常是求数列中连续子段和的最大值,经典的股票问题就是考察的这个思想及拓展。
例题:
AcWing:1054. 股票买卖
Leetcode:53. 最大子数组和

分治法O(nlogn)

此类问题时分适合采用分治思想,因为所有子区间 [ s t a r t , e n d ] [start, end] [start,end]只可能有以下三种可能:

  1. [ 1 , n 2 ] [1,\frac{n}{2}] [1,2n]这个区域内。
  2. [ n 2 + 1 , n ] [\frac{n}{2}+1, n] [2n+1,n]这个区域内。
  3. 左边界位于 [ 1 , n 2 ] [1,\frac{n}{2}] [1,2n],右边界位于 [ n 2 + 1 , n ] [\frac{n}{2}+1 ,n] [2n+1,n]内。
    在这里插入图片描述

这三种情况的最大值即为所求。前两种情况符合子问题递归特性,可以通过递归求出。

在第三种情况中 n 2 , n 2 + 1 \frac{n}{2},\frac{n}{2}+1 2n,2n+1必然包含在内,因此可以利用第二种穷举的思路分别向左右扩张求出。

int maxx = -INF;
int maxInterval(vector<int> a, int l, int r) {
	if(l == r) {
		return (a[l] > maxx) ? a[l] : maxx;
	}
	int sum_l = 0, sum_r = 0;
	int mid = (l + r) >> 1;
	sum_l = maxInterval(a, l, mid);
	sum_r = maxInterval(a, mid + 1, r);

	int s1 = 0, x = 0;
	for(int i = mid; i >= 0; i -- ) {
		x += a[i];
		if(x > s1) s1 = x;
	}
	int s2 = 0, y = 0;
	for(int i = mid + 1; i <= r; i ++ ) {
		y += a[i];
		if(y > s2) s2 = y;
	}
	maxx = max(sum_l, s1 + s2);
	maxx = max(maxx, sum_r);
	return maxx;
}

动态规划思路O(n)

如果我们用常规思路来枚举所有数字,并判断当前数字是否应该加入到最大子段;那么会发现,当前数字的选择与否并不是由前面已经遍历过的数字所决定,而是由其后面的数字来决定,这也就导致了问题的有后效性

当出现有后效性问题时,我们当前对子问题做出的选择就不一定为最优解,因为会受到后续数据的影响。

后效性问题是动态规划中一个非常重要的概念,在此引用《算法竞赛进阶指南》(李煜东著)中的一段话:

为了保证计算子问题能够按照顺序、不重复地进行,动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也被叫做无后效性。换言之,动态规划对状态空间的遍历构成一张有向无环图,遍历就是该有向无环图的一个拓扑序。有向无环图中的节点对应问题中的状态,图中的边则对应状态之间的转移,转移的选取就是动态规划中的决策

在此问题中,我们需要换一种思路来避免有后效性问题,我们可以将遍历到的数字看作必选项,然后判断是否要加上前面的和。我们考虑使用dp[i]来表示以a[i]来结尾的子数组的最大子段和,那么我们可以得到状态转移方程为:
d p [ i ] = m a x ( a [ i ] , d p [ i − 1 ] + a [ i ] ) dp[i] = max(a[i], dp[i - 1] + a[i]) dp[i]=max(a[i],dp[i1]+a[i])
那么结果即为: r e s = m a x ( r e s , d p [ i ] ) res=max(res, dp[i]) res=max(res,dp[i]).

int MaxInterval(vector<int> a, int len) {
	vector<int> dp(len);
	int res = -INF;
	dp[0] = a[0];
	for(int i = 1; i < len; i ++ ) {
		dp[i] = max(a[i], dp[i - 1] + a[i]);
		res = max(res, dp[i]);
	}
	return res;
}

扫描法O(n)

动态规划思路的一个空间优化版本

由于只和当前元素前面的最大值有关,因此只需要记录前面最大值即可。

前面的最大值表示前 i − 1 i-1 i1个问题的最优解。

int maxInterval(vector<int> v, int len) {
    int res = v[0], mi = min(0, v[0]), sum = v[0];
    for(int i = 1; i < len; i ++ ) {
        sum += v[i];
        res = max(res, sum - mi);
        mi = min(mi, sum);
    }
    return res;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/168896.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

网工内推 | 国企、港企网工,年底双薪,NA以上认证即可

01 中航期货有限公司 招聘岗位&#xff1a;信息技术部-网络工程师 职责描述&#xff1a; 1、负责总部、分支机构、外联单位网络的日常运维、故障和应急处置&#xff0c;特别是定期监测设备的运行状态&#xff0c;对存在隐患的地方及时发现改正&#xff0c;保持网络稳定通畅&am…

利用JDBC及Servlet实现对信息录入注册功能的实现

利用JDBC及Servlet实现对登录注册功能的实现&#xff1b; 1.题目要求&#xff1a; 1、新建一个数据库名为&#xff08;个人姓名拼音&#xff09;&#xff0c;表&#xff08;学生所在城市&#xff09;&#xff0c;字段&#xff08;sid&#xff1a;学号&#xff0c;sname&#x…

从硬件到软件:揭秘磁盘结构和文件系统组织

&#x1f4df;作者主页&#xff1a;慢热的陕西人 &#x1f334;专栏链接&#xff1a;Linux &#x1f4e3;欢迎各位大佬&#x1f44d;点赞&#x1f525;关注&#x1f693;收藏&#xff0c;&#x1f349;留言 本博客主要内容讲解了从磁盘的硬件结构&#xff0c;再到操作系统内部是…

采集1688整店商品(店铺所有商品、店铺列表api)

返回数据&#xff1a; 请求链接 {"user": [],"items": {"item": [{"num_iid": "738354436678","title": "国产正品i13 promax全网通5G安卓智能手机源头厂家批发手机","pic_url": "http…

Altium Designer内电层(Plan)GND和POWER出现的死铜如何去除-AD

1.问题描述 更多遇到的是顶层底层敷铜时出现清楚死铜&#xff1b;但是在内电层有时候也会出现死铜。这时候不去除死铜就会在DRC中报错。 2.解决办法1-多边形填充挖空 在工具栏&#xff1a; 放置——多边形填充挖空&#xff1b;然后再错误高亮处的死铜周围画多边形&#xff0c…

制作Go程序的Docker容器(以及容器和主机的网络问题)

今天突然遇到需要将 Go 程序制作成 Docker 的需求&#xff0c;所以进行了一些研究。方法很简单&#xff0c;但是官方文档和教程有些需要注意的地方&#xff0c;所以写本文进行记录。 源程序 首先介绍一下示例程序&#xff0c;示例程序是一个 HTTP 服务器&#xff0c;会显示si…

机器学习第10天:集成学习

文章目录 机器学习专栏 介绍 投票分类器 介绍 代码 核心代码 示例代码 软投票与硬投票 bagging与pasting 介绍 核心代码 随机森林 介绍 代码 结语 机器学习专栏 机器学习_Nowl的博客-CSDN博客 介绍 集成学习的思想是很直观的&#xff1a;多个人判断的结合往往比…

通信网络安全防护定级备案流程介绍(附流程图)

通信网络安全防护定级备案是拥有增值电信业务经营许可证并且有开展电信业务的企业要做的一件事情。刚接触这块的家人们在填报操作的时候可能对具体通信网络安全防护定级备案流程还不是很清楚&#xff0c;所以就给大家画张具体的流程图吧&#xff0c;可以更加直观的了解。 通信…

栈和队列知识点+例题

1.栈 1.1栈的概念及结构 栈&#xff1a;一种特殊的线性表&#xff0c;其只允许在固定的一端进行插入和删除元素的操作。进行数据插入和删除操作的一端成为栈顶&#xff0c;另一端成为栈底。遵守后进先出的原则&#xff08;类似于弹夹&#xff09; 压栈&#xff1a;栈的插入操…

【考研数学】正交变换后如果不是标准型怎么办?| 关于二次型标准化的一些思考

文章目录 引言一、回顾二次型的定义是什么&#xff1f;什么叫标准二次型&#xff1f;怎么化为标准型&#xff1f; 二、思考写在最后 引言 前阵子做了下 20 年真题&#xff0c;问题大大的&#xff0c;现在订正到矩阵的第一个大题&#xff0c;是关于二次型正交变换的。和常规不同…

『亚马逊云科技产品测评』活动征文|通过lightsail一键搭建Drupal VS 手动部署

『亚马逊云科技产品测评』活动征文&#xff5c;通过lightsail一键搭建Drupal 提示&#xff1a;授权声明&#xff1a;本篇文章授权活动官方亚马逊云科技文章转发、改写权&#xff0c;包括不限于在 Developer Centre, 知乎&#xff0c;自媒体平台&#xff0c;第三方开发者媒体等亚…

面试官:你能说说常见的前端加密方法吗?

给大家推荐一个实用面试题库 1、前端面试题库 &#xff08;面试必备&#xff09; 推荐&#xff1a;★★★★★ 地址&#xff1a;web前端面试题库 前言 本篇文章略微介绍一下前端中常见的加密算法。前端中常见的加密算法主要形式包括——哈希函数&#xff0c;对称…

图片叠加_图片压缩

图片叠加 try {/* 1 读取第一张图片*/File fileOne new File("1.png");BufferedImage imageFirst ImageIO.read(fileOne);/* 2读取第二张图片 */File fileTwo new File("2.png");BufferedImage imageSecond ImageIO.read(fileTwo);//创建一个最底层画…

Ftrans自动同步软件:满足企业级数据同步的需求

随着数字经济的发展&#xff0c;企业数字化的办公场景越来越复杂&#xff0c;其中一个急需解决的问题就是企业不同服务器之间的文件自动同步的需求。然而&#xff0c;目前市场上的同步软件通常有很多的缺点&#xff0c;让用户感到困扰。 1、数据安全&#xff1a;在同步数据的过…

Apache POI(Java)

一、Apache POI介绍 Apache POI是Apache组织提供的开源的工具包&#xff08;jar包&#xff09;。大多数中小规模的应用程序开发主要依赖于Apache POI&#xff08;HSSF XSSF&#xff09;。它支持Excel 库的所有基本功能; 文本的导入和导出是它的主要特点。 我们可以使用 POI 在…

起立科技(起鸿)在第25届高交会上展示透明OLED技术创新

第二十五届中国国际高新技术成果交易会 日期&#xff1a;2023年11月15日 地点&#xff1a;福田会展中心7号馆 深圳&#xff0c;2023年11月15日 — 起鸿科技&#xff0c;作为透明OLED领域的引领者&#xff0c;于今日参展了第二十五届中国国际高新技术成果交易会。这一展会将汇…

云计算赛项容器云2023搭建

部署容器云平台[5 分] 使 用 OpenStack 私 有 云 平 台 创 建 两 台 云 主 机 &#xff0c; 云 主 机 类 型 使 用 4vCPU/12G/100G 类型&#xff0c;分别作为 Kubernetes 集群的 Master 节点和 node 节点&#xff0c; 然后完成 Kubernetes 集群的部署&#xff0c;并完成 Istio …

MAC上修改mysql的密码(每一步都图文解释哦)

当你想要连接本机数据库时&#xff0c;是不是有可能突然忘记了自己的数据库密码? 在此文中&#xff0c;我们来详细解决一下如何去修改自己的数据库密码&#xff0c;并使用Navicat来连接测试 1.停止mysql服务 打开终端&#xff0c;键入命令,将mysql服务先停止掉&#xff0c;…

身份证阅读器和社保卡读卡器Harmony鸿蒙系统ArkTS语言SDK开发包

项目需求&#xff0c;用ArkTS新一代开发语言实现了在Harmony鸿蒙系统上面兼容身份证阅读器和社保卡读卡器&#xff0c;调用了DonseeDeviceLib.har这个读卡库。 需要注意的是&#xff0c;鸿蒙系统的app扩展名为.hap&#xff0c;本项目编译输出的应用为&#xff1a;entry-default…

4-1三个整数的最大数

#include<stdio.h> int main(){int a,b,c,t,max;printf("请输入三个数&#xff1a;");scanf("%d,%d,%d",&a,&b,&c);t(a>b)?a:b;max(t>c)?t:c;printf("输出三个数中最大是数字是&#xff1a;%d",max);return 0;}