注册 登录
每天一道算法题

第一章:计算最值,次最值

第二章:进制的转换

第三章:质数,水仙花,公约数

第四章:子序列问题

首页 > 每天一道算法题 > 第四章:子序列问题 > 4.1节:最大子序列和

4.1节:最大子序列和

薯条老师 2021-04-15 16:34:12 224590 0

编辑 收藏

广州番禺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。

图片.png

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(n2), 在本节内容中,薯条老师要介绍的是一个时间复杂度为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 最具实力的小班培训

来这里参加Python和Java小班培训的学员大部分都找到了很好的工作,平均月薪有11K,学得好的同学,拿到的会更高。由于是小班教学,所以薯条老师有精力把每位学员都教好。打算参加线下小班培训的同学,必须遵守薯条老师的学习安排,认真做作业和项目。把知识学好,学扎实,那么找到一份高薪的工作就是很简单的一件事。

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

扫码免费领取学习资料:



欢迎 发表评论:

请登录

忘记密码我要注册

注册账号

已有账号?请登录