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

2024-01-27 17:50:58

题目描述

例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。

给一个数组，返回它的最大连续子序列的和

思路：动态规划

# -*- coding:utf-8 -*-

class Solution:

    def FindGreatestSumOfSubArray(self, array):

        if not array:

            return 0

        dp = [array[0]]

        i = 1

        for num in array[1:]:

            if dp[i - 1] <= 0:

                dp.append(num)

            else:

                dp.append(dp[i - 1] + num)

            i += 1

        return max(dp)