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