文档章节

动态规划经典题目:最大连续子序列和

H
 HeroHY
发布于 2017/04/28 16:16
字数 432
阅读 170
收藏 2

 给定k个整数的序列{N1,N2,...,Nk },其任意连续子序列可表示为{ Ni, Ni+1, ..., Nj },其中 1 <= i <= j <= k。最大连续子序列是所有连续子序中元素和最大的一个,例如给定序列{ -2, 11, -4, 13, -5, -2 },其最大连续子序列为{11,-4,13},最大连续子序列和即为20。

算法四:动态规划法

 

        时间复杂度:O(N) 

        终于到了动态规划的部分了,这么一步一步走来,感受到了算法的无穷魅力。那么如何用动态规划来处理这个问题? 

        首先,我们重温将一个问题用动态规划方法处理的准则: 

        “最优子结构”、“子问题重叠”、“边界”和“子问题独立”。 

        在本问题中,我们可以将子序列与其子子序列进行问题分割。 

        最后得到的状态转移方程为:        

      

 

       MaxSum[i] = Max{ MaxSum[i-1] + A[i], A[i]}; 

        在这里,我们不必设置数组MaxSum[]。 

代码实现:

int MaxSubSequence(const int A[], int N)
{
	int ThisSum,MaxSum,j;
	ThisSum = MaxSum =0;
	for(j = 0;j < N;j++)
	{
		ThisSum += A[j];
		
		if(ThisSum > MaxSum)
			MaxSum = ThisSum;
		else if(ThisSum < 0)
			ThisSum = 0; 
	}
	return MaxSum; 
}

        在本代码实现中,ThisSum持续更新,同时整个过程,只对数据进行了一次扫描,一旦A[i]被读入处理,它就不再需要被记忆。(联机算法)

© 著作权归作者所有

下一篇: 分治法
H
粉丝 3
博文 162
码字总数 86832
作品 0
海淀
私信 提问
最大子数组和

原题   Find the contiguous subarray within an array (containing at least one number) which has the largest sum.   For example, given the array , the contiguous subarray has ......

一贱书生
2016/12/15
48
0
夕拾算法进阶篇:13)最大连续子序列(动态规划DP)

题目描述 给定K个整数的序列{ N1, N2, ..., NK },其任意连续子序列可表示为{ Ni, Ni+1, ..., Nj },其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个,例如给定序...

jiangpeng59
2017/02/05
0
0
动态规划

动态规划(Dynamic Programming) 本文包括: 动态规划定义 状态转移方程 动态规划算法步骤 最长非降子序列(LIS) 最大乘积子串 Unique Paths Unique Paths II Minimum Path Sum Triangle 最...

廖少少
2017/09/27
0
0
算法与数据结构(二):动态规划(DP)总结

版权声明:版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/Dbyfreedom https://blog.csdn.net/Dbyfreedom/article/details/89388883 1. 最长公共子序列 题目描...

dby_freedom
04/21
0
0
[DP]洛谷P1115最大子段和

题目来源 https://www.luogu.org/problemnew/show/P1115 题目描述 给出一段序列,选出其中连续且非空的一段使得这段和最大。 输入输出格式 输入格式: 第一行是一个正整数 NN ,表示了序列的...

Chicago_01
2018/08/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

全球第一时间响应:Rancher发布2.3.1,支持K8S CVE修复版本

北京时间2019年10月17日,Kubernetes发布了新的补丁版本,修复了新近发现的两个安全漏洞:CVE-2019-11253和CVE-2019-16276。Rancher第一时间响应,就在当天紧随其后发布了Rancher v2.3.1和R...

RancherLabs
20分钟前
3
0
EMQ X 规则引擎系列 (八)桥接消息到 MQTT Broker

桥接概念 桥接是一种连接多个 EMQ X 或者其他 MQTT 消息中间件的方式。不同于集群,工作在桥接模式下的节点之间不会复制主题树和路由表。桥接模式所做的是: 按照规则把消息转发至桥接节点;...

EMQX
24分钟前
4
0
《2019年上半年云上企业安全指南》详解安全建设最易忽视的问题!

《2019年上半年云上企业安全指南》是阿里云基于对云安全中心监测到的威胁情报进行分析,形成的一份云上企业安全建设指南。通过对云上企业安全建设现状及多维度威胁情报的分析,得出企业安全建...

开源中国小二
24分钟前
4
0
一天之际在于晨之KMP算法

(我觉得不需要明白原理,应该是在面试或者工作的时候,该想到用什么算法以及之后直接赋值我这里的代码就好了) 下面的情况我们第一时间考虑想到的是用KMP算法。 情况一:// ts字符串是否包...

木九天
27分钟前
3
0
如何通过反射机制创建对象?

1. 什么是反射? Java 反射机制在程序运行时,对于任意一个类,都能够知道这个类的所有属性和方法;对于任意一个对象,都能够调用它的任意一个方法和属性。这种动态的获取信息以及动态调用对...

happywe
27分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部