剑指30-连续子数组的最大和

Posted on | In |

题目描述

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

动态规划思想，可以参考股票的最大利润问题。

  • F(i)：以array[i]为末尾元素的子数组的和的最大值。
  • 则有F(i)=max(F(i-1)+array[i],array[i])
  • max(res,F(i))就是所求。
  • 子向量的长度至少是1，如果子向量长度可以为0，则F(i)>=0，公式略有不同。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # 在每次元素累加和小于0时，从下一个元素重新开始累加
        if len(array) == 0:
            return None
        sumlist = []
        for num in array:
            if len(sumlist)> 0 and sumlist[-1] > 0:
                temp = sumlist[-1] + num
            else:
                temp = num
            sumlist.append(temp)
        return max(sumlist)