Maximum Subarray && 动态规划详解

题目链接

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

解题思路：

        这是一道非常经典的动态规划的题目，用到的思路在别的动态规划题目中也很常用，所以我们以后称为”局部最优和全局最优解法“。
        基本思路是这样的:  在遍历每一步中，我们都要维护两个变量，一个是全局最优值，就是到当前元素为止最优的值；一个是局部最优值，就是必须包含当前元素的最优的值。
        接下来我们说说动态规划的递推式（这是动态规划最重要的步骤，递归式出来了，基本上代码框架也就出来了）。假设我们已知第i步的global[i]（全局最优）和local[i]（局部最优），那么第i+1步的表达式是：
local[i+1]=Math.max(local[i]+A[i], A[i])，就是局部最优值是一定要包含当前元素的，如果local[i]是负的，那么加上他就不如不加，所以不然就是直接用A[i]。
        有了当前一步的局部最优，那么全局最优值就是当前的局部最优或者还是原来的全局最优。即：global[i+1]=Math(local[i+1],global[i])

        接下来我们分析一下复杂度，时间上只需要扫描一次数组，所以时间复杂度是O(n)。空间上我们可以看出表达式中只需要用到上一步local[i]和global[i]就可以得到下一步的结果，所以我们在实现中可以用一个变量来迭代这个结果，不需要是一个数组，也就是如程序中实现的那样，所以空间复杂度是两个变量（local和global），即O(2)=O(1)。

python3代码实现：

class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 用来维护局部最优解和全局最优解
        local_v, global_v = nums[0], nums[0]
        for v in nums[1:]:
            local_v = max(v+local_v, v)
            global_v = max(local_v, global_v)
        return global_v