例子说明

输入的数组为{1, -2, 3, 10, -4, 7, 2, -5}，和最大的子数组为{3, 10, -4, 7, 2}。因此输出为该子数组的和18

我的第一想法

把所有的可能的子数组全部循环遍历出来，找出和最大的那个数据，记录，要用到双层循环

直接上代码

def cla(lyst):
    max_array = []
    max_sum = 0
    counter = 0
    for i in range(len(lyst)):
        for j in range(i+1, len(lyst)+1):
            sub_array = lyst[i:j]
            sub_sum = sum(sub_array)
            counter += 1
            if sub_sum > max_sum:
                max_array = sub_array
                max_sum = sub_sum
            elif sub_sum == max_sum:
                max_array.append(sub_array)
    print(max_array, max_sum)
    print(counter)


if __name__ == "__main__":
    cla([1, -2, 3, 10, -4, 7, 2, -5])

这种简单粗暴的方式耗费的时间是：

n+n-1+n-2+n-3+...+1 -> 1/2 * n^2 + 1/2 * n

时间复杂度应该是O(n^2)

第二次优化

思考一下这种规律，第一个数1，第二个数-2，和为-1，那么从外层循环1开始，内存循环在-2之后都是没有意义的了，因为前两个数的和为负数或0，和后面的数组成子数组的和肯定是比后面的数自己组成子数组更小或相等的，而在外层循环继续往后走的时候肯定也会碰到后续的子数组，即：[1, -2, 3]这样的子数组可以直接忽略，直接从[3]开始了

def cla(lyst):
    max_array = []
    max_sum = 0
    counter = 0
    for i in range(len(lyst)):
        for j in range(i+1, len(lyst)+1):
            sub_array = lyst[i:j]
            sub_sum = sum(sub_array)
            counter += 1
            if sub_sum <= 0:
                break;
            if sub_sum > max_sum:
                max_array = sub_array
                max_sum = sub_sum
            elif sub_sum == max_sum:
                max_array.append(sub_array)
    print(max_array, max_sum)
    print(counter)


if __name__ == "__main__":
    cla([1, -2, 3, 10, -4, 7, 2, -5])

第三次优化

这几天一直在看MOOC上浙江大学的数据结构讲课，讲到了这个问题。上面写的两个算法时间复杂度都是O(n^{2)，当我们每次看到O(n}2)这种类型的复杂度的时候，都要再思考是否可以优化成 nlog n。
采用分治法的思想，把数组每次分成两份，递归的分解，直到最后只有一个元素的时候，如果元素小于0就返回0，否则返回原值。分别计算中间点左右两边的最大和，同时还要考虑横跨中间点的和。

2019-07-03-01.png

# 分治法
# 算法复杂度：O(nlogn)
def cla(items, left, right):
    maxLeftSum = 0
    maxRightSum = 0
    leftBorderSum = 0
    rightBorderSum = 0
    maxLeftBorderSum = 0
    maxRightBorderSum = 0
    
    if left == right:
        if items[left] > 0:
            return items[left]
        else:
            return 0
    
    center = (left+right) // 2
    maxLeftSum = maxSubseqSum2(items, left, center)
    maxRightSum = maxSubseqSum2(items, center+1, right)

    # 左边最大和
    for i in range(center-1, left-1, -1):
        leftBorderSum += items[i]
        maxLeftBorderSum = max(leftBorderSum, maxLeftBorderSum)
    
    # 右边最大和
    for i in range(center, right+1):
        rightBorderSum += items[i]
        maxRightBorderSum = max(rightBorderSum, maxRightBorderSum)

    return max(maxLeftBorderSum+maxRightBorderSum, max(maxLeftSum, maxRightSum))

第四次优化

我觉得把我第二次优化的第二层循环去掉，在优化一下就是这个了，一直不明白贪心算法是什么意思，希望再接下来的学习中能理解。这样的话算法复杂度就降低到O(n)的水平了，nice啊~

# 贪心算法
# 算法复杂度：O(n)
def maxSubseqSum3(items):
    maxSum = tempSum = 0
    itemsLength = len(items)
    for i in range(0, itemsLength):
        tempSum += items[i]
        if tempSum > maxSum:
            maxSum = tempSum
        elif tempSum < 0:
            tempSum = 0
    print(maxSum)
    return maxSum

总结

当我们把一个算法复杂度修改到O(n^2)的时候，一定要再想想是不是能优化到 nlog n 的层次。

算法复杂度排名：n! > 2^n > n^3 > n^2 > nlog n > n > log n > 1

两段算法相加，复杂度 = 最大的算法复杂度
两段算法相乘，复杂度 = 两段算法复杂度相乘

来自 https://leejnull.github.io/2019/08/20/2019-07-03/