刷题记录 贪心算法-4：53. 最大子数组和

题目：53. 最大子数组和

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

• 1 <= n <= 8

一、模式识别

1.贪心算法

局部最优解：连续和为负时放弃连续和，重新开始连续和

局部到全局：选取多个子数组的最大连续和

反例：（象征性的写一下，能用贪心的都不会有，而且也不用证明）

代码随想录里也说这道题的贪心并不好想

不仅不好想，而且仔细想会发现连续和为负时放弃连续和只是一个必要条件，

2.动态规划

序列问题：经典动态规划问题，所以其实本题更容易想到动态规划解法

（1）定义：dp[i]: 以nums[i]为结尾的最大数字和

（2）递推公式：dp[i] = max(dp[i - 1] +num, num)

dp[i - 1]是以前一个数字为结尾的最大值，

由于连续数组条件限制，因此在本轮中只能在加入以前的连续序列或重新开始之间做出选择

（3）初始化：由递推，任意dp[i]依赖于dp[i - 1]，需要从dp[0]开始

（4）遍历顺序：由递推，dp[i]依赖于dp[i - 1]，需要从前往后

二、代码实现

1.暴力解法

连续子序列这么明确的条件，用两层嵌套循环分别表示起始点和终止点最容易实现了

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        ans = -inf
        for i, num in enumerate(nums):
            for j in range(i, n):
                sum_all = sum(nums[i: j + 1])
                if sum_all > ans:
                    ans = sum_all
        return ans

但有个缺点：会超时 

2.贪心算法

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        ans = -inf
        count = 0
        for i, num in enumerate(nums):
            count += num
            if count < num:
                count = num
            if count > ans:
                ans = count
        return ans

3.动态规划

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

三、动态规划与贪心算法的逻辑关系

仔细观察动态规划的递推公式dp[i] = max(dp[i - 1] +num, num)

dp[i - 1] +num和num的选择条件是是什么？

很明显是dp[i - 1]的值的正负号，与贪心算法连续和为负时放弃连续和的条件完全吻合

因此，本题的关键就在于理解“连续”：

由于只能对连续子数组求和，

对于每一个数字，只需要在与上一个数字的连续和相加和重新开始算连续和之间做出选择

而不需要考虑当前数字与哪些数字求和能得到最大值

所以实际上对于本题而言：

动态规划解法就是贪心算法的充分性证明，

贪心算法就是动态规划的精简版

以下是贪心算法到动态规划的一个过渡态写法：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        ans = -inf
        count = 0
        for i, num in enumerate(nums):
            count += num
            if count < num:
                count = num
            if count > ans:
                ans = count
        return ans

注意相比与贪心算法count的比较顺序是调换的