Python基础教程

第一章: 环境搭建,安装Python

第二章: 挑选一款趁手的IDE

第三章: 计算机基础知识

第四章: 命令行基础知识

第五章: 从全局把握Python

第六章: Python语言基础

第七章: Python流程控制

第八章: Python数据类型与运算

第九章: Python字符串类型

第十章: Python列表类型

第十一章: Python元组类型

第十二章: Python字典类型

第十三章: Python集合类型

第十四章: Python函数处理

第十五章: Python文件处理

第十六章: Python面向对象

第十七章: Python异常处理

第十八章: Python模块处理

第十九章: Python高级编程

第二十章: Python项目实战

首页 > Python基础教程 > 第十四章: Python函数处理 > 14.8节: 程序实战-最大子序列和

14.8节: 程序实战-最大子序列和

薯条老师 2022-12-06 14:19:04 23865 0

编辑 收藏

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

薯条老师在广州做Python和Java的小班培训,一个班最多10人,学员的平均就业薪资有11K。不在广州的同学可以报名线上直播班,跟线下小班的同学们同步学习。培训的课程有Python爬虫,Python后端开发,Python办公自动化,Python大数据分析,Python量化投资,Python机器学习,Java中高级后端开发。授课详情请点击:http://chipscoco.com/?cate=6

14.8.1 最大子序列和

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

图片.png

14.8.2 算法思路

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

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

在Python中实现这样的算法,需要使用嵌套的循环结构:

# __author__ = 薯条老师
import random

def max_subsequence_sum(data):
    """
    :param n: 包含n个数的列表
    :return: 最大连续子序列和
    """
    max_sum = data[0]
    length = len(data)
    for outer_index in range(length):
        sum_ = data[outer_index]
        max_sum = sum_ if sum_ > max_sum else max_sum
        for inner_index in range(outer_index+1, length):
            sum_ += data[inner_index]
            max_sum = sum_ if sum_ > max_sum else max_sum
    return max_sum
    
if __name__ == "__main__":
    numbers = [random.randint(-5, 5) for _ in range(4)]
    print("序列:{}\n最大连续子序列和:{}".format(numbers, max_subsequence_sum(numbers)))

以上算法的时间复杂度为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], 否则就是两者之和。

14.8.3 算法实现

# __author__ = 薯条老师
import random

def max_subsequence_sum(data):
    """
    :param data: 包含多个数的列表
    :return: 最大连续子序列和
    """
    max_sum = sum_ = data[0]
    if len(data) <=1:
        return max_sum
       
    for number in data[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)))

13.4.3 最具实力的小班培训

薯条老师在广州做Python和Java的小班培训,一个班最多10人。不在广州的同学可以报名线上直播班,跟线下小班的同学们同步学习。打算参加小班培训的同学,必须遵守薯条老师的学习安排,认真做作业和项目。把知识学好,学扎实,那么找到一份高薪的工作就是很简单的一件事。

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

扫码免费领取Python学习资料:


欢迎 发表评论: