当前位置:   article > 正文

python—四种方法求解最大连续子序列和_连续子序列和的最大值python_python连续最大和

python连续最大和

在这里插入图片描述

感谢每一个认真阅读我文章的人,看着粉丝一路的上涨和关注,礼尚往来总是要有的:

① 2000多本Python电子书(主流和经典的书籍应该都有了)

② Python标准库资料(最全中文版)

③ 项目源码(四五十个有趣且经典的练手项目及源码)

④ Python基础入门、爬虫、web开发、大数据分析方面的视频(适合小白学习)

⑤ Python学习路线图(告别不入流的学习)

网上学习资料一大堆,但如果学到的知识不成体系,遇到问题时只是浅尝辄止,不再深入研究,那么很难做到真正的技术提升。

需要这份系统化学习资料的朋友,可以戳这里获取

一个人可以走的很快,但一群人才能走的更远!不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人,都欢迎加入我们的的圈子(技术交流、学习资源、职场吐槽、大厂内推、面试辅导),让我们一起学习成长!

最简单的方法就是直接求解出所有的子序列之和,然后比较子序列之和,求出最大值。那么如何求解子序列呢?首先子序列的起始位置可能是任意的,结束位置也可以是任意的。可以一层循环确定子序列的起始位置,嵌套一层循环确定子序列的结束位置并求和,

def getMaxSubString(arr):
    sum_list = []
    for i in range(len(arr)):
        cur_sum = 0
        for j in range(i, len(arr)):
            cur_sum += arr[j]
            sum_list.append(cur_sum)
    max_element = max(sum_list)
    return max_element

if __name__ == '\_\_main\_\_':
    res = getMaxSubString([-2, 1, -3, 4, -1, 2, 1, -5, 4])
    print(res)

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
优化穷举

不使用一个额外的空间存在每次计算的子序列和,而是每次计算完成之后,直接比较大小

def getMaxSubSeqSum(arr):
    # sum\_list = []
    max_element = arr[0]
    for i in range(len(arr)):
        cur_sum = 0
        for j in range(i, len(arr)):
            cur_sum += arr[j]
            # sum\_list.append(cur\_sum)
            if cur_sum > max_element:
                max_element = cur_sum
    # max\_element = max(sum\_list)
    return max_element


if __name__ == '\_\_main\_\_':
    res = getMaxSubSeqSum([-2, 1, -3, 4, -1, 2, 1, -5, 4])
    print(res)


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
分治法

分治法是一种使用广泛的算法,其基本思想是:“如果整个问题比较复杂,可以将问题分化,各个击破”。分治包含“分”和“治”两个过程,先将问题分成两个大致相等的子问题,然后递归地对它们求解。

在此例中,先将序列等分成左右两份,最大子序列只可能出现在三个地方:

  1. 整个子序列出现在左半部分;
  2. 整个子序列出现在右半部分;
  3. 跨越左右边界出现在中间。

最大子序列和要么在左半部分,要么在右半部分,要么横跨左右两部分。所以分别求出这三种情况的最大序列和,比较求得最终的最大子序列和。左半部分和右半部分可以用递归求,那么只需要在函数中求解横跨两部分的最大子序列即可。从中间值开始,向前面两种方法那样,起始位置为中间下标,一部分向左求和,另一部分向右求和,最终两部分相加即可。因为在Python中组合数据类型可以不用声明全局,直接是地址传值,所以直接用了。

def divide\_and\_conquer(lst, left, right):
    if left == right:
        if lst[left] > 0:
            return lst[left]
        else:
            return 0

    center = (left + right) // 2
    # 左边界最大子序列和右边界最大子序列
    max_left_sum = divide_and_conquer(lst, left, center)
    max_right_sum = divide_and_conquer(lst, center + 1, right)

    max_left_border_sum = left_border_sum = 0
    for i in range(center, left - 1, -1):
        left_border_sum += lst[i]
        if left_border_sum > max_left_border_sum:
            max_left_border_sum = left_border_sum

    max_right_border_sum = right_border_sum = 0
    for i in range(center + 1, right + 1):
        right_border_sum += lst[i]
        if right_border_sum > max_right_border_sum:
            max_right_border_sum = right_border_sum

    # 左、右与跨越边界的子序列
    return max(max_left_sum, max_right_sum, max_left_border_sum + max_right_border_sum)


if __name__ == '\_\_main\_\_':
    lst = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    print(divide_and_conquer(lst, 0, len(lst)-1))

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
动态规划

如果你也是看准了Python,想自学Python,在这里为大家准备了丰厚的免费学习大礼包,带大家一起学习,给大家剖析Python兼职、就业行情前景的这些事儿。

一、Python所有方向的学习路线

Python所有方向路线就是把Python常用的技术点做整理,形成各个领域的知识点汇总,它的用处就在于,你可以按照上面的知识点去找对应的学习资源,保证自己学得较为全面。

二、学习软件

工欲善其必先利其器。学习Python常用的开发软件都在这里了,给大家节省了很多时间。

三、全套PDF电子书

书籍的好处就在于权威和体系健全,刚开始学习的时候你可以只看视频或者听某个人讲课,但等你学完之后,你觉得你掌握了,这时候建议还是得去看一下书籍,看权威技术书籍也是每个程序员必经之路。

四、入门学习视频

我们在看视频学习的时候,不能光动眼动脑不动手,比较科学的学习方法是在理解之后运用它们,这时候练手项目就很适合了。

四、实战案例

光学理论是没用的,要学会跟着一起敲,要动手实操,才能将自己的所学运用到实际当中去,这时候可以搞点实战案例来学习。

五、面试资料

我们学习Python必然是为了找到高薪的工作,下面这些面试题是来自阿里、腾讯、字节等一线互联网大厂最新的面试资料,并且有阿里大佬给出了权威的解答,刷完这一套面试资料相信大家都能找到满意的工作。

成为一个Python程序员专家或许需要花费数年时间,但是打下坚实的基础只要几周就可以,如果你按照我提供的学习路线以及资料有意识地去实践,你就有很大可能成功!
最后祝你好运!!!

网上学习资料一大堆,但如果学到的知识不成体系,遇到问题时只是浅尝辄止,不再深入研究,那么很难做到真正的技术提升。

需要这份系统化学习资料的朋友,可以戳这里获取

一个人可以走的很快,但一群人才能走的更远!不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人,都欢迎加入我们的的圈子(技术交流、学习资源、职场吐槽、大厂内推、面试辅导),让我们一起学习成长!

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/秋刀鱼在做梦/article/detail/805049
推荐阅读
相关标签
  

闽ICP备14008679号