30、最大连续子序列的和

题目描述
求最大连续子序列的和，序列中包含正负数。
例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

就是动归的思想了，假设F(N)代表是一第N个元素结尾的子序列的最大连续子序列的和。（注意，不是从0到N，而单单只是以N结尾）

最优子结构：

解释一下，对于F(N)来说，只有两种结果，一是接着用前面的子序列的值F(n-1)+nums[N]，另一个是重新从nums[N]开头作为子序列，接下来只需要从这里面选择最大值即可：

• 如果F(N-1)小于0，那么F(N-1)+nums[N]一定是小于nums[N]的，此时就令F(N) = nums[N]
• 如果F(N-1)大于0，那么F(N-1)+nums[N]一定是大于nums[N]的，此时就令F(N) = F(N-1)+nums[N]

代码实现：

# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        F_n = array[0]
        max = F_n
        for num in array[1:]:
            if F_n <= 0:
                F_n = num
            else:
                F_n += num

            #得到最大值
            if max < F_n:
                max = F_n
        return max