luoheng
8/31/2019 - 6:10 AM

序列最大子数组

def MaxSubsequenceSum(A):
    maxSum = -float("inf")
    c = 0
    for i in A:
        if c > 0:
            c += i
        else:
            c = i
        if c > maxSum:
            maxSum = c
    return maxSum

def main():
    A = [-2, 11, -4, 13, -5, -2]
    B = [-6, 2, 4, -7, 5, 3, 2, -1, 6, -9, 10, -2]
    print(MaxSubsequenceSum(A))
    print(MaxSubsequenceSum(B))

if __name__ == "__main__":
    main()