题解 | #连续子数组最大和#
连续子数组最大和
https://www.nowcoder.com/practice/1718131e719746e9a56fb29c40cc8f95
思路1：动态规划
1. 确定dp数组代表的含义
dp[i]：以下标 i 结尾的连续子数组的最大和
2. 确定递推公式
以 i 结尾的连续子数组的最大和为 以 i-1 结尾的连续子数组的最大和加上当前第 i 个元素 和 当前元素本身 中的最大值
故递推公式为：dp[i] = max(dp[i-1] + nums[i], nums[i])
3. 初始化
输入有正有负，所以可以将dp数组初始化为无穷小或者数组中的最小值
由递推公式可得所有状态都由上一状态推导而来，故需要初始化dp[0], 即dp[0] = nums[0]
代码：
n = int(input())
nums = list(map(int, input().split()))
dp = [float('-inf')] * n
dp[0] = nums[0]
for i in range(1, n):
dp[i] = max(nums[i], dp[i-1] + nums[i])
print(max(dp))
思路2：暴力解法（会超时）
代码：
n = input()
nums = list(map(int, input().split()))
tmp = float('-inf')
for i in range(len(nums)):
for j in range(i+1, len(nums)+1):
tmp = max(tmp, sum(nums[i:j]))
print(tmp)
查看6道真题和解析
农夫山泉工作强度 11人发布
