leetcode-53 最大子序和
题目
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
分析
第一感觉要用到动态规划,就需要找出状态和状态转移方程。找状态至关重要,状态找的好,对应的状态转移方程可能就非常简单,状态找的不好,对应的状态转移方程可能就比较麻烦。
找状态一般找问题本身或者问题的等价问题,先尝试以问题本身作为状态来分析,如果对应的状态转移方程很复杂,再根据问题尝试有没有其他的等价问题来作为状态
初步分析
首先以题目作为状态
f(n)为前n个元素的最大子序和的值
由于f(n)只是前n个元素中的最大子序和,这个子序可能并不包含nums[n]元素,所以再来一个nums[n+1]时,并不太好确定f(n+1),需要分如下2种情况来分析:
-
当最大子序包含nums[n],则f(n+1)的求解如下:
如果nums[n+1]>0 则f(n+1)=f(n)+nums[n+1] 如果nums[n+1]<0 则f(n+1)=f(n)
-
当最大子序不包含nums[n],则f(n+1)的求解如下:
来一个nums[n+1]只会对以nums[n]结尾的每个子序的最大和产生更新影响,同时如果前面的子序和都是负的话,则nums[n+1]则是最大子序和,所以只需要计算出这部分更新后的最大子序和与f(n)对比求最大值即为f(n+1)的最大子序和 即f(n+1)=max(f(n),以第n个元素结尾的最大子序和+nums[n+1],nums[n+1])
这里我们就会发现针对上述f(n)的状态转移方程还是非常复杂,并且状态转移方程里面还包含了一个暂时没有结论的问题即:以第n个元素结尾的最大子序。这个问题其实也是一个动态规划,这个问题的解如下:
g(n)为以第n个元素结尾的最大子序和,则g(n+1)的解如下:
当g(n)>0 则g(n+1)=g(n)+nums[n] 当g(n)<=0 则g(n+1)=nums[n]
所以这个g(n)问题还是很好求解的。
综上所述对于f(n)的求解是动态规划里面还嵌套动态规划,简述为父动态规划嵌套了子动态规划,不过还好,每一轮都可以求出这一轮的子动态规划值,然后利用这个值进而可以求出父动态规划的值。所以对于上述思路还是可以做出来结果的。
不过上述思路也太复杂了,很可能是我们选择的状态不合适导致的,所以此时我们就需要转换思路有没有更合适的状态
转换思路
等价命题的转换并没有太多的规律可循,与实际题目息息相关,可能需要从上面的初始分析中进行提取。
比如上面的g(n)还是很简单的,能否充分利用g(n)来解题?
假如我知道了每个g(n)的值,那么f(n)其实就是max(g(k)) 0<=k<=n
所以整个问题其实就清晰明了了很多,最终是以第N个元素结尾的最大子序和作为状态来进行动态规划,利用动态规划的结果来求解最终的问题
套路总结
- 很多时候动态规划的出题者不会给你一个一眼就能看出的状态,这时候就可能需要重新去找一个等价命题的状态,比如对于该题,你能够快速想到g(n)这个状态
- 假如想不到对应的等价命题的状态,看能否根据已有的简单的动态规划的解来求解问题,比如我已知了g(n),能够利用g(n)作为突破口来推导目标问题的答案
- 某个子序的解可能是所有以某个元素结尾的子序的解的max或者min等其他函数,以某个元素结尾的子序的解可以简化好多问题
代码
利用一个变量来记录g(n-1)的值,通过g(n-1)和状态转移方程来求解出g(n),同时用一个变量来记录g(n)的最大值即为f(n)
public static int maxSubArray(int[] nums) { int fn = nums[0]; int lastGn = nums[0]; for (int i = 1; i < nums.length; i++) { if (lastGn > 0) { lastGn += nums[i]; } else { lastGn = nums[i]; } if (lastGn > fn) { fn = lastGn; } } return fn; }
代码很简单,关键点不在于解决了此题,而是在于解决此题的思考过程,其中还是有一些套路可循的
跑分
欢迎关注微信公众号:乒乓狂魔

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
分布式工作流任务调度系统Easy Scheduler正式开源
分布式工作流任务调度系统Easy Scheduler正式开源 1、背景 在多位技术小伙伴的努力下,经过近2年的研发迭代、内部业务剥离及重构,也经历一批种子用户试用一段时间后,EasyScheduler终于迎来了第一个正式开源发布版本 -- 1.0.0。 相信做过数据处理的伙伴们对开源的调度系统如oozie、azkaban、airflow应该都不陌生,在使用这些调度系统中可能会有这样的体验:比如配置工作流任务不能可视化、任务的运行状态不能实时在线查看、 任务运行时不能暂停、不能支持参数传递、不能补数、不能多租户使用、调度系统不高可用等等问题所烦扰过。Easy Scheduler正是在这种背景下应运而生,其目标就是为使调度更加easy,更可以从其中文名“易调度”看出我们的初衷。 2、设计特点 Easy Scheduler是一个分布式工作流任务调度系统,主要解决数据研发ETL错综复杂的依赖关系所带来的各种问题。 其主要目标如下: 以DAG图的方式将Task按照任务的依赖关系关联起来,可实时可视化监控任务的运行状态 支持丰富的任务类型:Shell、MR、Spark、SQL(mysql、post...
- 下一篇
Spring Cloud Alibaba到底坑不坑?
之前我发过一篇《说说我为什么看好Spring Cloud Alibaba》,然后这两天有网友给我转了这篇文章《坑爹项目spring-cloud-alibaba,我们也来一个》,问我的看法是怎么样的,聊天时候简单说了一下。今天在家休息,抽空整理一下内容,逐点说一下我的看法,主要还是觉得这篇文章博眼球的成分高一些,因为这篇文章的解读与之前其他某些自媒体发布的《Eureka 2.0 开源工作宣告停止,继续使用风险自负》一文有异曲同工之“妙”,如果读者没有真正的理解Spring Cloud与Spring Cloud Alibaba,就很有可能会对它们有什么误解,然后产生这样的想法: 感觉很有道理,这东西真垃圾 标题很燃,必须转发 下面具体来说说该文章中,那些我认为不太正确的解读: 第一点:远程调用RPC 看看这篇文章的解读: SpringCloud默认的是Feign和Ribbon,主要是提供了远程调用请求和解析,以及负载均衡的功能。客观点来说,如果不用这两个组件,就会越来越四不像,干脆也别叫SpringCloud了,所以替换不得。 RPC会大量使用动态代理的功能,将你的字符串或者配置(因为网络...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- CentOS8编译安装MySQL8.0.19
- Docker安装Oracle12C,快速搭建Oracle学习环境
- Eclipse初始化配置,告别卡顿、闪退、编译时间过长
- CentOS8安装Docker,最新的服务器搭配容器使用
- Linux系统CentOS6、CentOS7手动修改IP地址
- 设置Eclipse缩进为4个空格,增强代码规范
- CentOS7,CentOS8安装Elasticsearch6.8.6
- CentOS8安装MyCat,轻松搞定数据库的读写分离、垂直分库、水平分库