广州番禺Python, Java小班周末班培训

薯条老师的线下Python小班办得很好，学员的平均就业薪资有11K。线下小班培训的课程有Python爬虫，Python后端开发，Python办公自动化，Python大数据分析，Python量化投资，Java中高级后端开发。授课详情请点击：http://chipscoco.com/?cate=6

4.1.1 问题说明

这里的最大子序列和是指在一个包含n(n>=1)个数字的序列中，计算最大的连续排列的子序列和。举个简单的例子，比如序列-1，1，2，3，由于第一个元素为负数，其它为正数，所以最大的连续子列一定是1,2,3。

4.1.2 算法思路

最容易想到的算法思路是在循环中计算所有的连续子序列的和(暴力枚举)：在循环中从第一个数开始，不断与下一个数累加，并与前一个累加和进行比较。第一趟遍历结束以后，再从第二个数开始继续累加求和。

继续以序列-1，1，2，3为例，在循环中首先遍历出元素-1，子序列和为-1，接着遍历出元素1, 子序列和为-1+1, 接着再遍历出元素2，子序列和为-1+1+2，以此类推。第一趟遍历结束以后，再以第2个元素1作为起始值继续累加求和。

在Python中实现这样的算法，需要使用嵌套的循环结构。以下为算法的核心代码：

for outer_index in range(length):
    for inner_index in range(outer_index, length):
        # 不断进行累加 
        pass

以上算法的时间复杂度为O(n²), 在本节内容中，薯条老师要介绍的是一个时间复杂度为O(n)的算法，该算法基于动态规划思想。该动态规划算法基于这样的思路，使用dp[i]表示以第i个数结尾的最大连续子序列和，于是存在以下递推公式：

dp[i] = max(n[i], dp[i-1]+n[i])

该公式表示以第i个数结尾的最大连续子序列和，要么是当前的数，要么是当前数之前的最大连续子序列和与该数相加。不难理解，如果dp[i-1]小于0，那么dp[i-1]+n[i]一定小于n[i], 否则就是两者之和。

4.1.3 算法实现

# __author__ = 薯条老师
import random

def max_subsequence_sum(n):
    """
    :param n: 包含n个数的列表
    :return: 最大连续子序列和
    """
    max_sum = sum_ = n[0]
    for number in n[1:]:
        sum_ = number if sum_ < 0 else sum_+number
        if sum_ > max_sum:
            max_sum = sum_
    return max_sum


        
if __name__ == "__main__":
    numbers = [random.randint(-5,  5) for _ in range(4)]
    print("序列:{}\n最大连续子序列和:{}".format(numbers, max_subsequence_sum(numbers)))

4.1.4 最具实力的小班培训

(1) Python后端工程师高薪就业班，月薪11K-18K，免费领取课程大纲
(2) Python爬虫工程师高薪就业班，年薪十五万，免费领取课程大纲
(3) Java后端开发工程师高薪就业班，月薪11K-20K, 免费领取课程大纲
(4) Python大数据分析，量化投资就业班，月薪12K-25K,免费领取课程大纲

扫码免费领取学习资料：