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

连续子数组最大和

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)



全部评论

相关推荐

那一天的Java_J...:他本来公司就是做这个的,不就是正常的游戏客户端和服务器开发,软硬件联动,有啥恶心不恶心的,提前告诉你就是怕你接受不了,接受不了就没必要再往后走流程浪费时间,虽然这公司是一坨。
点赞 评论 收藏
分享
白火同学:能。我当初应届沟通了1200,收简历50,面试10左右吧,加油投吧
投了多少份简历才上岸
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

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