# -*- coding:utf-8 -*-
class Solution:
    """
    题目描述

    HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。
    今天测试组开完会后,他又发话了:在古老的一维模式识别中,
    常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。
    但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？
    例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。
    你会不会被他忽悠住？(子向量的长度至少是1)
    """

    def FindGreatestSumOfSubArray(self, array):
        # 典型的动态规划问题
        # 状态转移方程为 包含当前元素的最大子段和 = MAX(之前的最大字段和 + 当前元素 , 当前元素)
        # 通俗一点说就是一直累加,一旦累加的结果小于0,就重新开始计算.
        MaxSum = -999
        Sum = -999
        for number in array:
            Sum = max(Sum + number, number)
            MaxSum = max(MaxSum, Sum)
        return MaxSum
