文档章节

最大连续子序列和-动态规划

fengsehng
 fengsehng
发布于 2016/11/09 09:13
字数 524
阅读 23
收藏 0

题目描述:

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

注意:

最大连续子序列和如果为负,则返回0;而本题目中的最大连续子序列和并不返回0,如果是全为负数,则返回最大的负数即可。

思路分析:

-具有最优子结构,和重叠子问题, 动态规划的算法思路

  • 最大连续子序列和只可能是以位置0~n-1中某个位置结尾。当遍历到第i个元素时,判断在它前面的连续子序列和是否大于0,如果大于0,则以位置i结尾的最大连续子序列和为元素i和前门的连续子序列和相加;否则,则以位置i结尾的最大连续子序列和为元素i。
    -

状态转移方程: sum[i]=max(sum[i-1]+a[i],a[i])

代码:

int maxsequence3(int a[], int len)  
{  
    int maxsum, maxhere;  
    maxsum = maxhere = a[0];   //初始化最大和为a【0】 
    for (int i=1; i<len; i++) {  
        if (maxhere <= 0)  
            maxhere = a[i];  //如果前面位置最大连续子序列和小于等于0,则以当前位置i结尾的最大连续子序列和为a[i] 
        else  
            maxhere += a[i]; //如果前面位置最大连续子序列和大于0,则以当前位置i结尾的最大连续子序列和为它们两者之和 
        if (maxhere > maxsum) {  
            maxsum = maxhere;  //更新最大连续子序列和 
        }  
    }  
    return maxsum;  
}  

我的微信二维码如下,欢迎交流讨论

这里写图片描述

欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧,都是干货!

微信订阅号二维码如下:

这里写图片描述

参考:
http://blog.csdn.net/sgbfblog/article/details/8032464
http://blog.csdn.net/zmazon/article/details/8247015

    -

© 著作权归作者所有

fengsehng
粉丝 4
博文 284
码字总数 214494
作品 0
朝阳
程序员
私信 提问
动态规划经典题目:最大连续子序列和

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

HeroHY
2017/04/28
163
0
LeetCode基础算法-动态规划

LeetCode基础算法-动态规划 LeetCode 动态规划 动态规划的核心步骤: 查看大问题的最优解能否使用小问题的最优解lai来解决。 如果能解决,那么总结出大问题的最优解和小问题最优解之间的关系...

24K男
2018/09/11
0
0
动态规划算法之:最长公共子序列 & 最长公共子串(LCS)

1、先科普下最长公共子序列 & 最长公共子串的区别: 找两个字符串的最长公共子串,这个子串要求在原字符串中是连续的。而最长公共子序列则并不要求连续。 2、最长公共子串 其实这是一个序贯决...

大数据之路
2013/03/25
53.5K
2
最大子数组和

原题   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
47
0
夕拾算法进阶篇:13)最大连续子序列(动态规划DP)

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

jiangpeng59
2017/02/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

使用CSS自定义属性构建骨架屏

写在前面 几天前看到薄荷前端团队分享的《前端骨架屏方案小结》,突然回想起一年前看到的max bock写的《Building Skeleton Screens with CSS Custom Properties》,翻译整理写下出此文,分享...

前端老手
昨天
7
0
Docker常用命令小记

除了基本的<font color="blue">docker pull</font>、<font color="blue">docker image</font>、<font color="blue">docker ps</font>,还有一些命令及参数也很重要,在此记录下来避免遗忘。 ......

程序员欣宸
昨天
5
0
MAT使用-jvm内存溢出问题分析定位

1.MAT简介: MAT 全称 Eclipse Memory Analysis Tools 是一个分析 Java堆数据的专业工具,可以计算出内存中对象的实例数量、占用空间大小、引用关系等,看看是谁阻止了垃圾收集器的回收工作,...

xiaomin0322
昨天
5
0
内网和外网之间的通信(端口映射原理)

首先解释一下“内网”与“外网”的概念: 内网:即所说的局域网,比如学校的局域网,局域网内每台计算机的IP地址在本局域网内具有互异性,是不可重复的。但两个局域网内的内网IP可以有相同的...

Jack088
昨天
6
0
3.深入jvm内核-原理、诊断与优化-4. GC算法和种类

一、GC算法和种类 GC的概念 GC算法 引用计数法 标记清除 标记压缩 复制算法 可触及性 Stop-The-World GC的对象是堆空间和永久区 引用计数法 老牌垃圾回收算法 通过引用计算来回收垃圾 使用者...

hexiaoming123
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部