最大子序和
目录
题目
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
分析
看到“最”字很容易联想到dp, 下面我们试着去推导出递推公式。 假设数组为s,s[i]表示第i号元素,f[i]表示到第i号元素的具有最大和的连续子数组的最大和
$\begin{aligned}
& f[0] = -2 \
& f[1] = 1 + max(f[0], 0) = 1 \
& f[2] = -3 + max(f[1], 0) = -2 \
& f[3] = 4 + max(f[2], 0) = 4 \
& …
\end{aligned}$
因为要求连续f[i]如果最大,f[i-1]必须是正数才行,所以可以推导出递推公式 $f[i] = max(f[i-1], 0) + s[i], i > 0$
代码
|
|