您现在的位置是:首页 > 正文

python实现连续子序列最大和问题(动态规划)

2024-02-01 04:50:38阅读 3

说明:子列表指的是列表中索引(下标)连续的元素构成的列表;列表中的元素是int类型,可能包含正整数、0、负整数;程序输入列表中的元素,输出子列表元素求和的最大值,例如:
输入:1 -2 3 5 -3 2

输出:8

输入:0 -2 3 5 -1 2

输出:9

输入:-9 -2 -3 -5 -3

输出:-2

如题,对于原列表a,假设元素a[i]为所求子列表的最后一个元素,则所求子列表有两种情况:
1)不含a[i]之前的元素
2)含有a[i]之前的序列(该序列为之前累加得到)
所以求解过程为:对列表中每一个元素作出上述假设并分别求解两种情况,并比较记录最大值。

具体实现如下,时间复杂度O(n),空间复杂度O(1):

def maxSubList(items):
    size = len(items)
    _sum = _max = items[0]
    for i in range(1, size):
        #如果前面序列和的结果小于零 则丢弃(即从两种情况中取最大值)
        _sum = max(

网站文章

  • flex布局

    flex布局

    总结一下flex布局

    2024-02-01 04:50:31
  • java 动态创建类_Java运行时动态生成类几种方式

    最近一个项目中利用规则引擎,提供用户拖拽式的灵活定义规则。这就要求根据数据库数据动态生成对象处理特定规则的逻辑。如果手写不仅每次都要修改代码,还要每次测试发版,而且无法灵活根据用户定义的规则动态处理逻...

    2024-02-01 04:50:24
  • antv图例出现分页_Echarts和highCharts图表使用总结(附AntV)

    Echarts:1.给y轴上间隔线设置成虚线yAxis: {type: 'value',boundaryGap: [0, '100%'],axisLine: {show...

    2024-02-01 04:49:54
  • 「NodeJs」nodejs 定时任务

    nodejs 定时访问网页。

    2024-02-01 04:49:47
  • std::forward()

    std::forward()完美转发。

    2024-02-01 04:49:38
  • freekan电影系统后台无法登录解决方法

    freekan电影系统后台无法登录解决方法

    这个freekan电影系统真的比较挑主机,不只是试了许多主机无法安装,有时安装上了明明账号密码正确还登录不上,但又找不到更好用的电影系统。幸亏我用的是老薛主机,售后非常给力,联系他们后立马就解决了,他...

    2024-02-01 04:49:32
  • SpringMvc+Mybatis +Oracle

    +Mybatis入门笔记http://www.cnblogs.com/hellokitty1/p/5216025.htmljsp运行原理JSP运行原理及运行过程https://blog.csdn.net/hanxuemin12345/article/details/23831645转载于:https://www.cnblogs.com/maowuyu-xb/p/9126367....

    2024-02-01 04:49:02
  • EasyExcel——自定义注解、实现动态获取下拉框内容

    EasyExcel——自定义注解、实现动态获取下拉框内容

    主要展示了在使用easyexcel导出过程中如何从数据库表获取动态下拉框内容,以及和固定下拉框内容的对比

    2024-02-01 04:48:56
  • Redis集群

    Redis集群

    Redis集群是一个提供在多个Redis节点间共享数据的程序集,可以支持多个Master。

    2024-02-01 04:48:50
  • 记一次生产环境GitLab服务和数据迁移到阿里云和GitLab版本升级

    记一次生产环境GitLab服务和数据迁移到阿里云和GitLab版本升级

    GitLab是一个用于管理代码的仓库系统,他是一个开源项目,使用Git作为代码管理工具,并在此基础上搭建起来的Web服务,可通过Web界面进行访问公开的或者私人项目。它拥有与Github类似的功能,能够浏览源代码,管理代码缺陷和注释。.........

    2024-02-01 04:48:20