Python算法与数据结构--求所有子数组的和的最大值

栏目: 数据库 · 发布时间: 6年前

内容简介:玄魂工作室秘书 玄魂工作室

Python算法与数据结构--求所有子数组的和的最大值

Python算法与数据结构--求所有子数组的和的最大值

玄魂工作室-玄魂

玄魂工作室秘书 玄魂工作室 昨天

题目:输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。

求所有子数组的和的最大值。要求时间复杂度为O(n)。

这个题目有多个解法,比如可以用一个二维数组存之前每个数据的和,然后在进行大小比较;但是这样时间负责度就是O(n2)了。

换个思路思考下,因为是要最大数,那么就不需要存储,只需要找最大值就可以了。但是为了找子序列的最大和,在遇到相加为负数的情况要跳过,这块注意代码中最后一个if的注释。

基本思路:一个数一个数相加,相加后和最大数以及当前这个数对比,找出最大的;如果相加后是负数,则累加清零

代码-----------

# -*- coding: utf-8 -*-
"""
题目:输入一个整形数组,数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
基本思路:一个数一个数相加,相加后和最大数以及当前这个数对比,找出最大的;如果相加后是负数,则累加清零
"""

if __name__ == "__main__":   
    #初始化数组,测试数据
    #dataList = [-3,-10,30,-5,-6,-100,300]
    #dataList = [-3,-10,-30,-5,-6,-1,-100,-300]
    #dataList = [-3,-10,0,-5,-6,-100,-300]
    dataList = [3,10,0,5,6,100,300]
    #dataList = [0,0,0,0,0,0,0]
    #prd_data用来记录前面累加的数,一旦累加值是负数,则清零
    pre_data = dataList[0]
    #用来记录最大值
    max_data = pre_data
    #遍历数据组进行累加和大小对比
    for i in range(len(dataList)):       
        currData = dataList[i]
        #第一个数用来做初始化,从第二个数开始算
        if i==0:
            continue
        else:
            #相加后进行temp_data,max_data以及currData的大小对比,找出最大的
            temp_data = currData + pre_data
            if temp_data > currData:
                if temp_data > max_data:
                    max_data = temp_data
            else:
                if currData > max_data:
                    max_data = currData
            #如果相加后是负数,则清0,因为一旦出现负数在相加只会让最大值变小
            #这块注意**********一定是相加后是负数,而不是这个数本身是负数***********
            #因为本身是负数,但是相加后是正数,对后面的数据增大还是有帮助的
            if temp_data > 0:
                pre_data = temp_data
            else:
                pre_data = 0

    print max_data

精品网络安全视频推荐 - 传说的黑麒麟

精品网络安全课推荐--《密码安全攻防技术精讲》

web安全入门课程推荐--Web 安全恩仇录:漏洞原理

欢迎关注玄魂工作室垂直订阅号 “白话算法”。

Python算法与数据结构--求所有子数组的和的最大值

优质算法课程推荐,扫码了解详情:

Python算法与数据结构--求所有子数组的和的最大值


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

编程之法

编程之法

July / 人民邮电出版社 / 2015-9-1 / 49.00元

本书涉及面试、算法、机器学习三个主题。书中的每道编程题目都给出了多种思路、多种解法,不断优化、逐层递进。本书第1章至第6章分别阐述字符串、数组、树、查找、动态规划、海量数据处理等相关的编程面试题和算法,第7章介绍机器学习的两个算法—K近邻和SVM。此外,每一章都有“举一反三”和“习题”,以便读者及时运用所学的方法解决相似的问题,且在附录中收录了语言、链表、概率等其他题型。书中的每一道题都是面试的高......一起来看看 《编程之法》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

在线进制转换器
在线进制转换器

各进制数互转换器

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码