连续子数组的最大和

"""
动态规划: 其基本思想是将待求解问题分解成若干个子问题,
先求解子问题，然后从这些子问题的解得到原问题的解
"""


def func(li):
    """
    问题: 
    对于一个长度为 n 的数组, 求连续子数组的最大和

    核心: 
    如果 li[i] 前面的所有数字(子数组)之和小于 li[i],
    那么前面的子数组放弃, 从当前数字 li[i] 重新开始求和

    思路: 
    利用动态规划算法, 将长度为 n 的数组, 拆解成两部分 li[0] 和 li[1:],
    再将 li[1:] 拆解成 li[1:][0] 和 li[1:][1:], 以此类推
    """

    # 1、首先, 姑且认为第一个数字是最大的, 比剩余所有元素的累积还要要大
    max_sum = li[0]
    # 2、其次, 定义一个临时变量, 记录真正的最大和
    tmp = 0

    # 3、然后, 遍历整个数组
    for i in li:

        # 4、接着, 用临时变量 tmp (初始值为0) + 当前数字后与当前的数字比大小
        # 就是说如果前面的一系列数字(子数组)之和都不如当前的数字大,
        # 则抛弃子数组保留(赋值给 tmp )当前数字, 否则反之
        tmp = max(tmp + i, i)

        # 5、最后, 判断一下我们认为的最大和(max_sum) 
        # 与真正的最大和(不断遍历累加并判断后被赋值的 tmp) 哪个大
        max_sum = max(max_sum, tmp)

    return max_sum


def main():
    li = [1, -2, 3, 10, -4, 7, 2, -5]
    print(func(li))

    li = [2]
    print(func(li))

    li = [-10]
    print(func(li))


if __name__ == '__main__':
    main()