连续子数组的最大和

题目描述

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

思路

这是一道动态规划题目。对于数组的第i个元素，在这个位置的连续最大和有两种情况。第一种情况，前面的连续最大和加上当前元素。第二种情况，当前元素自己反而比第一种情况大。 比如-1，-2，100。这个数组里，对于100而言，肯定是不算前面的负数的情况下取值最大。那么，对于n个元素的数组中的每个元素而言，以该元素为结尾的最大连续子数组和的情况就是f(i)=max(f(i-1)+array[i],array[i])。要么是以上一位结尾的连续子数组加上自己，要么就只有自己。

代码

def FindGreatestSumOfSubArray(self, array):
        # write code here
        if len(array) < 0:
            return 0
        f = [] #f[i]第i个结尾处的最大值
        result = []
        f.append(array[0])
        result.append(array[0])
        for i in range(1,len(array)):
            val = max(array[i],f[i-1]+array[i])
            f.append(val)
        ans = max(f)
        return ans