给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
自我未通过题解
这题卡了我很久，一直超时。我知道这肯定是需要用动态规划解答，但就是勾画不出合适的最优子结构。
我是直接从最优原问题着手分解，即 ”求数组的最大和连续数组“， 所以，怎么从中去分解出最优子问题呢？
思路一：连续子数组有很多种组合，似乎需要把所有组合都算一遍，看看哪个最大。
我通过一次遍历，先把 sum(nums[0:i]), i = 0,1,2…n-1, 都计算出来，
然后再以此计算出所有其他结果，如 sum(nums[1:i]) = sum(nums[0:i]) - nums[0]
似乎是可行的，但此算法时间复杂度是 O(n^2), 不符合题意
思路二：那还可以怎么去勾画子问题呢？ f(x, y) = max(nums[x], f(x+1, y)) ?
这样也是不行的。因为子问题1的结果对于子问题2是没有意义的。
如 f(x+1, y) 的最优连续子数组 是 [x+3, y-3]
然而 f(x, y) 的最优解连续子数组有可能是包含 nums[x]的， 如 [x, x+2]
被 子问题1 抛弃的元素，又被 子问题2 拾起了。
动态规划 题解
我的思路是：原最优问题 -> 分解最优子问题 -> 无果失败
力扣题解的思路是： 原最优问题 -> 转换成一个更简单最优问题，
这个最优问题，会得到一个集合，集合中的最大值就是原最优问题的最优解
也难怪我想破脑袋都想不到呢。看得出来，这是一个很实用的 将问题简单化的技巧:
原问题很棘手，可以将其转换成另一个好处理的问题，从这个问题的解中，能很简单的计算出原问题的解
下面来说一下，力扣题解转换的问题：
原问题：求数组中大和连续数组
转换的问题：求数组中 以每个元素结尾 的最大和连续数组
这个问题会得到 len(nums) 个解，其中最大的就是原问题的最优解
求解：数组中 以每个元素结尾 的最大和连续数组
设 f(i) 为以 i 结尾的最大和连续数组，很容易勾画出最优子问题: f(i) = max(f(i-1) + nums[i], nums[i])
可以以此写出自顶向下的递归算法，因为每个子问题都只会计算一次，因此，不需要加入备忘机制
class Solution2:
def maxSubArray(self, nums: List[int]) -> int:
self.nums = nums
self.max_sum = self.nums[0]
self.set_max_subsum_endwith(len(nums) - 1)
return self.max_sum
def set_max_subsum_endwith(self, i):
if i == 0:
return self.nums[i]
self.nums[i] = max(self.set_max_subsum_endwith(i - 1) + self.nums[i], self.nums[i])
if self.nums[i] > self.max_sum:
self.max_sum = self.nums[i]
return self.nums[i]
写出了自顶向下的算法，便可以很轻松写出自底向下的算法
class Solution4:
def maxSubArray(self, nums: List[int]) -> int:
max_sum = nums[0]
for i in range(1, len(nums)):
if nums[i - 1] > 0:
nums[i] += nums[i - 1]
if nums[i] > max_sum:
max_sum = nums[i]
return max_sum