【LeetCode】53. 最大子数组和

1 问题

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

子数组 是数组中的一个连续部分。

示例 1：

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

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

2 答案

这题直接不会

再次尝试，动态规划问题，首先思考第二个状态和第一个状态的转移方程，比较容易找到思路

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) < 2: return nums[0]
        dp = [0] * len(nums)
        dp[0] = nums[0]
        for i in range(len(nums)):
            dp[i] = max(dp[i-1]+nums[i], nums[i])
        return max(dp)
1
2
3
4
5
6
7
8

官方解，动态规划，对应两个状态转移方程，分别为

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        size = len(nums)
        if size == 0:
            return 0
        dp = [0 for _ in range(size)]

        dp[0] = nums[0]
        for i in range(1, size):
            if dp[i-1] >= 0:
                dp[i] = dp[i-1] + nums[i]
            else:
                dp[i] = nums[i]
        return max(dp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

或

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        size = len(nums)
        pre = 0
        res = nums[0]
        for i in range(size):
            pre = max(nums[i], pre+nums[i])
            res = max(pre, res)
        return res
1
2
3
4
5
6
7
8
9

还有一种方法，分治法，即分类讨论，暂不研究

3 知识点

动态规划，步骤一般为，定义子问题，定义状态转移方程，定义初始状态，定义输出

简单的动态规划问题，很有可能问的问题就可以设计成为子问题，复杂的动态规划问题就没有那么容易看出子问题应该如何设计了，这需要一定的解决问题的经验。

这里状态的定义不是题目中的问题的定义，不能直接将最后一个状态返回回去。

状态转移方程
d p [ i ] = { d p [ i − 1 ] +  nums  [ i ] ,  if  d p [ i − 1 ] > 0  nums  [ i ] ,  if  d p [ i − 1 ] ≤ 0 d p[i]=\left\{dp[i−1]+ nums [i], if dp[i−1]>0 nums [i], if dp[i−1]≤0

\right. dp[i]={dp[i−1]+ nums [i], nums [i],​ if  if ​dp[i−1]>0dp[i−1]≤0​
或
d p [ i ] = max ⁡ { d p[i]=\max \{ dp[i]=max{ nums $[i],dp[i-1]+$ nums $[i]\}$

https://leetcode.cn/problems/maximum-subarray/solutions/9058/dong-tai-gui-hua-fen-zhi-fa-python-dai-ma-java-dai/