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

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

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

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算法与数据结构--求所有子数组的和的最大值


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

查看所有标签

猜你喜欢:

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

Design and Analysis of Distributed Algorithms (Wiley Series on P

Design and Analysis of Distributed Algorithms (Wiley Series on P

Nicola Santoro / Wiley-Interscience / 2006-10-27 / USD 140.95

This text is based on a simple and fully reactive computational model that allows for intuitive comprehension and logical designs. The principles and techniques presented can be applied to any distrib......一起来看看 《Design and Analysis of Distributed Algorithms (Wiley Series on P》 这本书的介绍吧!

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

各进制数互转换器

URL 编码/解码
URL 编码/解码

URL 编码/解码

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换