题目
-
给你一个整数数组 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
动态规划
def maxSubArray(nums):
n = len(nums)
if n == 0:
return 0 # 空数组的最大子数组和为0
dp = [0] * n # 创建一个长度为n的数组来保存动态规划的状态
dp[0] = nums[0] # 第一个元素作为初始值
for i in range(1, n):
dp[i] = max(nums[i], nums[i] + dp[i - 1])#计算以索引 i 结尾的子数组的最大和，即 dp[i]。这个值可以通过比较当前元素 nums[i] 和当前元素与前一个子数组的和 nums[i] + dp[i - 1] 的大小，取较大值作为 dp[i] 的值。
res = float('-inf') # 初始化结果为负无穷
for i in range(n):
res = max(res, dp[i]) # 更新最大和的结果
return res
优化
def maxSubArray(nums):
n = len(nums)
if n == 0:
return 0 # 空数组的最大子数组和为0
dp_0 = nums[0] # 初始化动态规划的状态，第一个元素作为初始值
dp_1 = 0
res = dp_0
for i in range(1, n):
# dp[i] = max(nums[i], nums[i] + dp[i-1])
dp_1 = max(nums[i], nums[i] + dp_0)
dp_0 = dp_1
# 同时计算最大的结果
res = max(res, dp_1)
return res