最大连续子序列和

描述

给定一个数组,求出最大的连续子序列和

思路

在任何讲动态规范的地方都能找到求最大连续子序列和的例子。具体来说,假设数组为a[i],因为最大连续的子序列和必须是在位置0-(n-1)之间的某个位置结束。那么,当循环遍历到第i个位置时,如果其前面的连续子序列和小于等于0,那么以位置i结尾的最大连续子序列和就是第i个位置的值即a[i]。如果其前面的连续子序列和大于0,则以位置i结尾的最大连续子序列和为b[i] = max{ b[i-1]+a[i],a[i]},其中b[i]就是指最大连续子序列的和。

代码

def maxSum(list_of_nums):
    maxsum = 0
    maxtmp = 0
    for i in range(len(list_of_nums)):
        if maxtmp <= 0:
            maxtmp = list_of_nums[i]
        else:
            maxtmp += list_of_nums[i]

        if(maxtmp > maxsum):
            maxsum = maxtmp

    return maxsum

if __name__ == '__main__':
    list_of_num = [1,3,-3,4,-6]
    maxsum = maxSum(list_of_num)
    print "maxsum is: ",maxsum

来源

https://blog.csdn.net/bitcarmanlee/article/details/51526010

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习和数学

[编程经验] Python 中列表list介绍

列表是Python中非常重要的一种数据结构,使用频率非常高,本文主要介绍对于学习python的新手来说,需要掌握的一些基础知识。 1. 创建列表 ? 列表用中括...

40450
来自专栏逆向技术

C语言第六讲,数组

          C语言第六讲,数组 一丶什么是数组 数组,就是一整块的连续内存空间. 且类型都是一样的.大小一样 比如: ? 1.1数组元素的访问 我们要访...

60530
来自专栏机器学习算法工程师

算法题系列之二:求最大子数组之积

题目描述: 给定一个长度为N的整数数组,只允许用乘法,计算任意(N-1)个数的组合中乘积最大的一组。 算法分析: 动态规划的做法,假设数组为a[N],ma...

28860
来自专栏大闲人柴毛毛

动态规划法(三)——最长公共子序列

问题描述 给定两个序列,求出它们的最长公共子序列。 如:序列X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a},则X和Y的最长公共子...

38540
来自专栏猿人谷

C++ STL算法系列3---求和:accumulate

 该算法在numeric头文件中定义。 假设vec是一个int型的vector对象,下面的代码: //sum the elements in vec start...

23780
来自专栏Jack-Cui

第七天、判断三角形的类型

    根据输入的三角形的三条边判断三角形的类型,并输出它的面积和类型。 C代码: /*第七天、判断三角形的类型*/ #include <stdio.h> ...

22700
来自专栏数据结构与算法

P1062 数列

题目描述 给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列,例如,当k=3时,这个序列是: 1,3,4,9,...

31270
来自专栏mathor

C++STL中vector使用策略(一)

12150
来自专栏一英里广度一英寸深度的学习

Python 传值还是传引用

如果 node =None,相当于node指向一个不可变对象,在调用insert函数时,仅传值。

29630
来自专栏深度学习之tensorflow实战篇

python高阶函数:map(f,[list]),reduce(f,[list],可选初始值),

map,reduce和filter三个函数在python3和python2中发生了较大的差异。具体请看文章后面部分。 1. python的map()函数 ...

35140

扫码关注云+社区

领取腾讯云代金券