最大子序列和

547 次访问 2020-11-24

Walker

给定一个整数数组 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

原题链接：https://leetcode-cn.com/problems/maximum-subarray

自我未通过题解

动态规划 题解

动态规划题解