30、最大连续子序列的和

2018-10-04  本文已影响0人  小碧小琳

题目描述
求最大连续子序列的和,序列中包含正负数。
例如:{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]开头作为子序列,接下来只需要从这里面选择最大值即可:

代码实现:

# -*- 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
上一篇 下一篇

猜你喜欢

热点阅读