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

学好 Python 不论是就业还是做副业赚钱都不错，但要学会 Python 还是要有一个学习规划。最后大家分享一份全套的 Python 学习资料，给那些想学习 Python 的小伙伴们一点帮助！

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

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

二、学习软件

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

三、全套PDF电子书

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

四、入门学习视频

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

五、实战案例

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

六、面试资料

我们学习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

动态规划

当前的最大子序列和一定是由之前的最大子序列和加上（或不考虑）当前元素构成的。那么我们从第一个元素开始，假设第一个元素为目前的最大子序列和，下一个最大子序列一定是这个子序列加上第二个元素或者丢掉第一个元素。那么何时加上第二个元素呢？只要第一个元素不为负数（因为负数只会越加越小，根本不会构成最大子序列和），那么就是第一个子序列和加上这个元素。如果是负数，那么目前最大的子序列的起始位置只能是这个元素。这样每次循环都得到目前最优的子序列，知道循环结束。
回归到第一种方法，每次循环都是起始位置的确定的，结束位置也是在循环不断变化中。此方法是在每次循环中起始位置（可能）和结束位置都在变化。

def getMaxSubSeqSum(arr):


### 最后

不知道你们用的什么环境，我一般都是用的Python3.6环境和pycharm解释器，没有软件，或者没有资料，没人解答问题，都可以免费领取（包括今天的代码），过几天我还会做个视频教程出来，有需要也可以领取~  

给大家准备的学习资料包括但不限于：  

Python 环境、pycharm编辑器/永久激活/翻译插件  

python 零基础视频教程  

Python 界面开发实战教程  

Python 爬虫实战教程  

Python 数据分析实战教程  

python 游戏开发实战教程  

Python 电子书100本  

Python 学习路线规划

![](https://img-blog.csdnimg.cn/d29631674929476f9c3b30f7ff58dff0.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaTM0Nzc5NTc5MA==,size_16,color_FFFFFF,t_70)




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

**[需要这份系统化学习资料的朋友，可以戳这里获取](https://bbs.csdn.net/topics/618317507)**

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

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
33
34
35
36
37