题解 | #连续子数组最大和#
连续子数组最大和
https://www.nowcoder.com/practice/1718131e719746e9a56fb29c40cc8f95
n = int(input()) nums = list(map(int, input().split())) dp = [0 for i in range(n)] dp[0] = nums[0] for i in range(1, n): dp[i] = max(dp[i-1]+nums[i], nums[i]) print(max(dp))
一直想用二维数组实现来着的,但是没必要
dp[i] = max(dp[i-1]+nums[i], nums[i])本道题的dp数组: [1, -1, 3, 13, 9, 16, 18, 13]
由于要求的是连续的子数组,所以如果和会被负数加得比当前值要小,就选择当前值,否则就得加上,巧妙的实现了“截断”“连续子数组”
