No.53 最大子序和

题目：给定一个整数数组nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
例：

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

题解：
一、DP贪心法

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if not nums:return -1<<31
        cur_sum=max_sum=nums[0]
        for i in range(1,len(nums)):
            cur_sum=max(nums[i],nums[i]+cur_sum)
            max_sum=max(max_sum,cur_sum)
        return max_sum

知识点：
贪心算法思想

贪心算法一般按如下步骤进行：
①建立数学模型来描述问题。
②把求解的问题分成若干个子问题。
③对每个子问题求解，得到子问题的局部最优解 。
④把子问题的解局部最优解合成原来解问题的一个解。
贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心算法不要回溯。

在本题中，我们要求的目标是最大子序和。因此我们维护两个值：当前的临时序列和，以及至今为止最大的子序和。
在遍历数组的每一步中，贪心地根据当前数组值更新临时序列和（原则是排除掉和为负数的临时序列），然后贪心地在临时序列和与此前的最大子序和中选择最大者，以此更新最大子序和。此处使用贪心算法只需要遍历一次数组，并且只需要维护常数个临时变量，因此时间复杂度为，空间复杂度为。

如何确定贪心算法可以得到全局最优解？
证明：
https://leetcode-cn.com/problems/maximum-subarray/solution/suan-fa-you-xiao-xing-de-yan-ge-zheng-ming-by-a_ru/

二、动态规划**

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n=len(nums)
        for i in range(1,n):
            if nums[i-1]>0:
                nums[i]+=nums[i-1]
        return max(nums)

知识点：
动态规划思想
和贪婪算法相似，核心原则是一致的，即摘去和为负数的子列。

三、分治法

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        #递归终止条件
        if n == 1:
            return nums[0]
        else:
            #递归计算左半边最大子序和
            max_left = self.maxSubArray(nums[0:len(nums) // 2])
            #递归计算右半边最大子序和
            max_right = self.maxSubArray(nums[len(nums) // 2:len(nums)])

        #计算中间的最大子序和，从右到左计算左边的最大子序和，从左到右计算右边的最大子序和，再相加
        max_l = nums[len(nums) // 2 - 1]
        tmp = 0
        for i in range(len(nums) // 2 - 1, -1, -1):
            tmp += nums[i]
            max_l = max(tmp, max_l)
        max_r = nums[len(nums) // 2]
        tmp = 0
        for i in range(len(nums) // 2, len(nums)):
            tmp += nums[i]
            max_r = max(tmp, max_r)
        #返回三个中的最大值
        return max(max_right,max_left,max_l+max_r)

作者：pandawakaka
链接：https://leetcode-cn.com/problems/maximum-subarray/solution/bao-li-qiu-jie-by-pandawakaka/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

知识点：
分治思想
对于分治法，需要考虑两个问题：
一、对于一个子问题，需要维护哪些变量？
二、如何合并两个子问题的结果？

这本题中，合并两个子区间的最大子序列，存在几种情况：（设端点分别为）



分别计算这三种情况下的最大子序列，然后取其中最大者为合并结果即可。
接下来的问题就是如何计算这三种情况的值：
对于每一个子问题，维护它的最大左子列、最大右子列、最大中子列、序列和。
对于第一种情况，
存在两种可能：（左边最大左子列、左边序列和）和（左边序列和+右边最大左子列），二者取最大者。
对于第二种情况，
同理，存在两种可能：（左边最大右子列、右边序列和）和（右边序列和+右边最大右子列），二者取最大者。
对于第三种情况，
只需要将左边最大右子列与右边最大左自列相加即可。
计算得到三种情况以后取最大者的值即可，不需要记录索引位置。这样就完成了左右两个子区间的合并。