动态规划-最大连续子序列和_最大连续子序列和 动态规划 时间复杂度

在刷力扣题的时候遇到了一个连续子数组最大和问题，下面是题目的链接和描述：

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

时间复杂度要求为n，因此不能采用穷举遍历的方法，下面介绍两种方法：分治法（nlogn）、动态规划（n）

1.分治法

分而治之。假如我们有一个很复杂的大问题，很难直接解决它，但是我们发现可以把问题划分成子问题，如果子问题规模还是太大，并且它还可以继续划分，那就继续划分下去。直到这些子问题的规模已经很容易解决了，那么就把所有的子问题都解决，最后把所有的子问题合并，我们就得到复杂大问题的答案了。

接下来分析这个问题：
首先，我们可以把整个序列平均分成左右两部分，答案则会在以下三种情况中：

1. 所求序列完全包含在左半部分的序列中。
2. 所求序列完全包含在右半部分的序列中。
3. 所求序列刚好横跨分割点，即左右序列各占一部分。

前两种情况和大问题一样，只是规模小了些，如果三个子问题都能解决，那么答案就是三个结果的最大值。第一和第二个小问题比较简单，可以利用递归表示，主要是第三个问题的分析：

只要计算出：以分割点为起点向左的最大连续序列和、以分割点为起点向右的最大连续序列和，这两个结果的和就是第三种情况的答案。因为已知起点，所以这两个结果都能在O(N)的时间复杂度能算出来。

def maxsum(nums):
    if len(nums) == 1:
  
1
2