LeetCode 第 53 题：连续子数组的最大和

动态规划 分治法

传送门：53. 最大子序和。

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

示例:

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

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

分析：

总结：分类讨论的标准是：若之前的和小于 0，则将最大和置为当前值，否则计算最大和。

思路1：动态规划

下面展示了标准的动态规划的写法。

Java 代码：

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int n = array.length;
        if (n == 0) {
            return 0;
        }
        int[] dp = new int[n];
        dp[0] = array[0];
        int res = array[0];
        for (int i = 1; i < n; i++) {
            dp[i] = Integer.max(dp[i - 1] + array[i], array[i]);
            res = Integer.max(res, dp[i]);
        }
        return res;
    }
    public static void main(String[] args) {
        int[] nums = new int[]{6, -3, -2, 7, -15, 1, 2, 2};
        Solution solution = new Solution();
        int findGreatestSumOfSubArray = solution.FindGreatestSumOfSubArray(nums);
        System.out.println(findGreatestSumOfSubArray);
    }
}

这道题主要就在状态的定义上要思考一下，这里题目中的关键字是“连续”，所以如果我们定义的状态就是题目要求的结果：dp[i] 表示 nums 在区间 [0,i] 中连续子数组的最大和，那么在思考状态转移方程的时候，dp[i] 之前的，例如 dp[i-1] 就有可能是是更前面的连续子数组的最大和，不利于我们分类讨论。

因此，我们可以定义状态：dp[i] 表示以 nums[i] 结尾的连续子数组的最大和。

这样定义状态，分类讨论就变得容易多了，因为 dp[i-1] 表示一定以 nums[i-1] 结尾，那么 dp[i] 就可以有两种情况：

1、把 nums[i] 直接接在 dp[i-1] 表示的那个数组的后面；

例如，dp[i-1] = 3，nums[i] = 5，当然接在后面，越接越大。

2、单独的一个 nums[i] 。

这种情况也比较好想到，比如：dp[i-1] = -3，nums[i] = 5，加上前面的数反而我越来越小了，干脆我另起炉灶吧。

以上两种情况的最大值就是 dp[i] 的值。

最后不要忘记了，最终的结果应该是把所有的 dp[0]，dp[1]，……，dp[n-1] 都看一遍，求最大值。

重点：动态规划问题。状态是：以当前数字为结尾的连续子数组的最大和。

Python 代码：

class Solution(object):
    def maxSubArray(self, nums):
        """
            :type nums: List[int]
            :rtype: int
            """
        l = len(nums)
        if l == 0:
            return 0
        if l == 1:
            return nums[0]
        dp = [0 for _ in range(l)]
        dp[0] = nums[0]
        for i in range(1, l):
            dp[i] = max(dp[i - 1] + nums[i], nums[i])
            # 最后不要忘记拉通求一遍最大值，或者在上面遍历的时候，就保存最大值
            return max(dp)

或者你可以在遍历的时候，就把最大值求出来。

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        l = len(nums)
        if l == 0:
            return 0
        # 以索引 i 结尾的最大子数组的和
        end_i_max = nums[0]
        # 最后返回的数
        res = nums[0]
        for i in range(1, l):
            # 例：[-3,1]
            end_i_max = max(nums[i], end_i_max + nums[i])
            res = max(res, end_i_max)
        return res

思路2：分治法

参考资料：连续子数组最大和

Python 写法：

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n == 0:
            return 0
        return self.__max_sub_array(nums, 0, n - 1)
    def __max_sub_array(self, nums, left, right):
        if left == right:
            return nums[left]
        mid = left + (right - left) // 2
        return max(self.__max_sub_array(nums, left, mid),
                   self.__max_sub_array(nums, mid + 1, right),
                   self.__max_cross_array(nums, left, mid, right))
    def __max_cross_array(self, nums, left, mid, right):
        """
        一定包含 nums[mid] 元素的最大连续子数组的和
        思路是看看左边扩散到底，得到一个最大数
        右边扩散到底得到一个最大数
        :param nums:
        :param mid:
        :param right:
        :return:
        """
        ls = 0
        j = mid - 1
        s1 = 0
        while j >= left:
            s1 += nums[j]
            ls = max(ls, s1)
            j -= 1
        rs = 0
        j = mid + 1
        s2 = 0
        while j <= right:
            s2 += nums[j]
            rs = max(rs, s2)
            j += 1
        return ls + nums[mid] + rs
if __name__ == '__main__':
    s = Solution()
    nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    result = s.maxSubArray(nums)
    print(result)

（本节完）