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

根据题意，求解连续数组的最大值，利用动态规划的思想，则可创建动态数组，然后赋值初始值，再根据状态转移方程进行遍历；本题中求解的是连续数组的最大值，设 dp[i] 表示数组 data[:i] 的最大值, 其值与 dp[i - 1] 和 当前值 data[i] 有关, 若 dp[i - 1] + data[i] > data[i] 则 dp[i] 由 dp[i - 1] + data[i] 转移得到, 如果 dp[i - 1] + dp[i] <= data[i] 则 dp[i] 与当前值有关; 初始值 dp[0] = data[0];代码如下：

n = int(input().strip())
data = list(map(int, input().strip().split()))
dp = [float('-inf') for _ in range(n)]
dp[0] = data[0]
for i in range(1, n):
    if dp[i - 1] + data[i] > data[i]:
        dp[i] = dp[i - 1] +data[i]
    else:
        dp[i] = data[i]
print(max(dp))

由于 dp[i] 的值只和当前值和 dp[i - 1] 有关，可用变量代替dp, 最终取整个数组的最大连续子数组的值，再用变量存储最大值，代码如下

n = int(input().strip())
data = list(map(int, input().strip().split()))
m, r = data[0], data[0]
for d in data[1:]:
    m = max(m + d, d)
    r = max(m, r)
print(r)