连续子数组的最大和

题目描述

在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和

方法描述

• 先把第一个值记录为最大值
• 判断下一个值加上后值不值当
• 判断上一步选择的值和目前的最大哪个打

python代码

def main():
    # 输入字符串转换成数组
    arr = input()
    arr_group = arr.split(" ")
    arr_number = []
    for item in arr_group:
        arr_number.append(int(item))
    temp = arr_number[0]
    res = temp
    n = len(arr_number)
    if n<1:
        print(0)
    else:
        for i in range(1,n):
            # 当前值加上后有没有不加大
            temp = max(temp+arr_number[i],arr_number[i])
            # 判断当前情况后，再比较和之前的哪个大
            res = max(temp,res)
        print(res)


if __name__ == '__main__':
    main()


# 1 2 -3 3 4 -5 -5 -6 -7