本文共 492 字，大约阅读时间需要 1 分钟。

题目：输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n).

这个题如果不考虑时间复杂度的话，可以直接用穷举法遍历所有的子数组的和，保存其最大值，思路非常简单。

class Solution:    def FindGreatestSumOfSubArray(self, array):        # write code here        max_sub = array[0]        for i in range(len(array)):            for j in range(len(array)-i):                if sum(array[i:i+j+1]) > max_sub:                    max_sub = sum(array[i:i+j+1])        return max_sub

在考虑时间复杂度的情况下，似乎就比较困难一些，在讨论区看到了好多动态规划的思想，感觉有点看不懂，暂时忽略...（偷个懒）

转载地址：https://blog.csdn.net/sinat_42437278/article/details/117447954 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！