题解 | #连续子数组最大和#

连续子数组最大和

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)



全部评论

相关推荐

能干的三文鱼刷了10...:公司可能有弄嵌入式需要会画pcb的需求,而且pcb能快速直观看出一个人某方面的实力。看看是否有面试资格。问你问题也能ai出来,pcb这东西能作假概率不高
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务