《剑指offer》笔记 - 第5章 优化时间和空间效率

子序列最大和问题

题目：有一个整形数组，元素有正有负，求一个连续子数组要求和最大。

常规解法：

从头开始一个一个累加，如果和为正则保存下来作为最大值的候选者，如果和为负就抛弃掉重置计数。

动态规划解法：

$$f(i)=\left\{ \begin{aligned} oData[i] & & j=0或者f(i-1)\le0 \\ f(i-1)+pData[i] & & i\neq0并且f(i-1)>0 \\ \end{aligned} \right.$$

解释

待补充。 $P_{173}$