本题多解，非常巧妙！都了解一下！
Leetcode Link: 53. 最大子数组和 - 力扣（LeetCode） 剑指 Offer 42. 连续子数组的最大和 - 力扣（LeetCode）
题目
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
解法一
思路：自己的想法
譬如说对于例 1 序列 [-2,1,-3,4,-1,2,1,-5,4]，我们知道它的答案是 [4,-1,2,1] 的和，难点在于什么时候应该新开始计算一个子序列的和，抛弃之前累加的子序列的和？
显然，新来一个数字 val，我们在考虑是不是把他加入到当前子序列中，需要它对这个和有贡献。但是这样想就有问题，显然答案中 -1 对和没有贡献，但是后面的贡献能够消除 -1 的影响，所以不能扔掉 -1，那应该怎么办呢？
我们从新来的 val 来考虑，对于这个 val，什么时候他不应该算上一个子序列里？显然，如果当前这个 val 加上之前的子序列比自己都要小，那么我 val 为什么要自贬身价，和之前的子序列合并呢？而是应该算作一个新的子序列的开始！
那么怎么找到子序列的最大和呢？显然这个和是一直变化的。到目前我没有想到最好的一步到位的方法，可以在每一步都算一下max(res, tmp_sum)，不过可以确定的是，当新开始子序列的时候，当前的res一定会是val
题解：
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
tmp_sum = nums[0] # 题目中输入长度一定 > 0
res = tmp_sum
for val in nums[1:]:
# "我"+前面的子序列和比"我"还小，所以"我"自立门户
if val + tmp_sum <= val:
tmp_sum = val
res = max(res, val)
else:
tmp_sum += val
res = max(res, tmp_sum)
return res
解法二
随想录的思路，贪心在和为负数的负数的时候直接抛弃，和我的思路一样，不过我的可能稍微好想一点?
和解法 1 的区别 解法一：思考当前这个要还是开辟一个新的 解法二：思考当前的这个和要还是用新的。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
cur_sum = 0
res = -float('inf')
p = 0
while(p < len(nums)):
if cur_sum < 0:
cur_sum = nums[p]
else:
cur_sum += nums[p]
p += 1
res = max(res, cur_sum)
return res解法三
思路：动态规划
dp 五步走
- 确定下标和内容的意义：dp[i]：包括下标 i 之前的最大连续子序列和为 dp[i]
- 递推公式：由前一个位置 dp[i-1]+nums[i]推出，如果比自己还小，则是自己 nums[i]，即 dp[i] = max (dp[i-1]+nums[i], nums[i])
- dp 数组初始化：dp[0] = nums[0]
- 遍历顺序：正向
- 举例推导 dp 数组
题解：
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
dp = [0] * len(nums)
dp[0] = nums[0]
for i in range(1, len(nums)):
dp[i] = max(nums[i], nums[i]+dp[i-1])
return max(dp)